wojiaocbj

Untitled

Apr 19th, 2022
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.24 KB | None | 0 0
  1. /*
  2.  Author: 曹北健
  3.  Result: AC Submission_id: 4330317
  4.  Created at: Sat Apr 16 2022 21:18:51 GMT+0800 (China Standard Time)
  5.  Problem_id: 5578   Time: 448   Memory: 7276
  6. */
  7.  
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include <math.h>
  11. #include <string.h>
  12. #include <ctype.h>
  13. #include <assert.h>
  14. #pragma warning(disable:4996)
  15. //void *bsearch(const void *key,const void *base,size_t count,size_t size,int (*compare)(const void *,const void *));
  16. //c++ upper_bound lower_bound
  17. void *lowerbound(void *key, void *base, size_t count, size_t itemsize, int(*compare)(const void *, const void *)){
  18.     size_t lo = 0, hi = count - 1, mid = 0;
  19.     if(compare(key, (char *)base + hi * itemsize) > 0){
  20.         return (char *)base + count * itemsize;
  21.     }
  22.     char *pmid = 0;
  23.     while(lo < hi){
  24.         mid = (lo + hi) >> 1;
  25.         pmid = ((char *)base) + mid * itemsize;
  26.         if(compare(pmid, key) < 0){
  27.             lo = mid + 1;
  28.         }
  29.         else{
  30.             hi = mid;
  31.         }
  32.     }
  33.     return (char *)base + lo * itemsize;
  34. }
  35. void *upperbound(void *key, void *base, size_t count, size_t itemsize, int(*compare)(const void *, const void *)){
  36.     size_t lo = 0, hi = count - 1, mid;
  37.     if(compare(key, (char *)base + hi * itemsize) >= 0){
  38.         return (char *)base + count * itemsize;
  39.     }
  40.     char *pmid = 0;
  41.     while(lo < hi){
  42.         mid = (lo + hi) >> 1;
  43.         char *pmid = ((char *)base) + mid * itemsize;
  44.         if(compare(pmid, key) <= 0){
  45.             lo = mid + 1;
  46.         }
  47.         else{
  48.             hi = mid;
  49.         }
  50.     }
  51.     return (char *)base + lo * itemsize;
  52. }
  53. int a[1919810] = { 0 };
  54. int compare(const void *p, const void *q){
  55.     int x = *((int *)p), y = *((int *)q);
  56.     if(x > y){
  57.         return 1;
  58.     }
  59.     else if(x < y){
  60.         return -1;
  61.     }
  62.     else{
  63.         return 0;
  64.     }
  65. }
  66. int main(){
  67. #ifdef _DEBUG
  68.     FILE *fp = freopen("../../../input.txt", "r", stdin);
  69.     //FILE *fp2 = freopen("output.txt", "w", stdout);
  70. #endif // _DEBUG
  71.     int n, i, m, key0, *find0;
  72.     scanf("%d%d", &n, &m);
  73.     for(i = 0; i < n; i++){
  74.         scanf("%d", a + i);
  75.     }
  76.     qsort(a, n, sizeof(int), compare);
  77.     while(m--){
  78.         scanf("%d", &key0);
  79.         find0 = lowerbound(&key0, a, n, sizeof(int), compare);
  80.         if(*find0 == key0){
  81.             printf("%d\n", (find0 - a) + 1);
  82.         }
  83.         else{
  84.             printf("-1\n");
  85.         }
  86.     }
  87. #ifdef _DEBUG
  88.     freopen("CON", "r", stdin);
  89.     //freopen("CON", "w", stdout);
  90.     system("pause");
  91. #endif // _DEBUG
  92.     return 0;
  93. }
Advertisement
Add Comment
Please, Sign In to add comment