Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Author: 曹北健
- Result: AC Submission_id: 4330317
- Created at: Sat Apr 16 2022 21:18:51 GMT+0800 (China Standard Time)
- Problem_id: 5578 Time: 448 Memory: 7276
- */
- #include <stdio.h>
- #include <stdlib.h>
- #include <math.h>
- #include <string.h>
- #include <ctype.h>
- #include <assert.h>
- #pragma warning(disable:4996)
- //void *bsearch(const void *key,const void *base,size_t count,size_t size,int (*compare)(const void *,const void *));
- //c++ upper_bound lower_bound
- void *lowerbound(void *key, void *base, size_t count, size_t itemsize, int(*compare)(const void *, const void *)){
- size_t lo = 0, hi = count - 1, mid = 0;
- if(compare(key, (char *)base + hi * itemsize) > 0){
- return (char *)base + count * itemsize;
- }
- char *pmid = 0;
- while(lo < hi){
- mid = (lo + hi) >> 1;
- pmid = ((char *)base) + mid * itemsize;
- if(compare(pmid, key) < 0){
- lo = mid + 1;
- }
- else{
- hi = mid;
- }
- }
- return (char *)base + lo * itemsize;
- }
- void *upperbound(void *key, void *base, size_t count, size_t itemsize, int(*compare)(const void *, const void *)){
- size_t lo = 0, hi = count - 1, mid;
- if(compare(key, (char *)base + hi * itemsize) >= 0){
- return (char *)base + count * itemsize;
- }
- char *pmid = 0;
- while(lo < hi){
- mid = (lo + hi) >> 1;
- char *pmid = ((char *)base) + mid * itemsize;
- if(compare(pmid, key) <= 0){
- lo = mid + 1;
- }
- else{
- hi = mid;
- }
- }
- return (char *)base + lo * itemsize;
- }
- int a[1919810] = { 0 };
- int compare(const void *p, const void *q){
- int x = *((int *)p), y = *((int *)q);
- if(x > y){
- return 1;
- }
- else if(x < y){
- return -1;
- }
- else{
- return 0;
- }
- }
- int main(){
- #ifdef _DEBUG
- FILE *fp = freopen("../../../input.txt", "r", stdin);
- //FILE *fp2 = freopen("output.txt", "w", stdout);
- #endif // _DEBUG
- int n, i, m, key0, *find0;
- scanf("%d%d", &n, &m);
- for(i = 0; i < n; i++){
- scanf("%d", a + i);
- }
- qsort(a, n, sizeof(int), compare);
- while(m--){
- scanf("%d", &key0);
- find0 = lowerbound(&key0, a, n, sizeof(int), compare);
- if(*find0 == key0){
- printf("%d\n", (find0 - a) + 1);
- }
- else{
- printf("-1\n");
- }
- }
- #ifdef _DEBUG
- freopen("CON", "r", stdin);
- //freopen("CON", "w", stdout);
- system("pause");
- #endif // _DEBUG
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment