allia

круговой массив

Oct 25th, 2020 (edited)
956
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cmath>
  3.  
  4. using namespace std;
  5.  
  6. int vvod (int x)
  7. {
  8.   cout.flush();
  9.   int y;
  10.   cout << "?" << " " << x << endl;
  11.   cin >> y;
  12.   return y;
  13. }
  14. int bin (int znach, int left, int right)
  15. {
  16.  int i = 0;
  17.  int index_elem = -1;
  18.  int middle;
  19.  
  20. while (left < right)
  21. {
  22.   i = (left + right) / 2;
  23.  middle = vvod (i);
  24.  
  25.     if (middle < znach)
  26.     left = i+1;
  27.     else right = i;
  28.  
  29. }
  30.  
  31.  middle = vvod (right);
  32.  
  33.   if (middle == znach)
  34.   index_elem = right;
  35.  
  36. return index_elem;
  37. }
  38.  
  39. int poisk (int raznica, int left, int right)
  40. {
  41.  int index = 0;
  42.  int i=(right + left)/2;
  43.  int middle = 0;
  44.  
  45. middle = vvod (i);
  46.  
  47.   int tek_raznica = middle - i;
  48.  
  49.   if (tek_raznica < raznica)
  50.     {
  51.       right = i;
  52.       if (right - left == 1)
  53.        index = left;
  54.       else
  55.        return poisk (raznica, left, right);
  56.     }
  57.   if (tek_raznica >= raznica)
  58.     {
  59.       left = i;
  60.       if (right - left == 1)
  61.         index = left;
  62.       else
  63.         return poisk (raznica, left, right);
  64.       }
  65.  return index;
  66. }
  67.  
  68. int main()
  69. {
  70.   cout.flush();
  71.   int n = 0, m = 0, first_elem, last_elem, middle, past_middle, index, znach, k;
  72.   cin >> n >> m;
  73.   cin >> znach;
  74.  
  75.   first_elem = vvod(1);
  76.   last_elem = vvod (n);
  77.  
  78.   if (last_elem > first_elem)
  79.   index = n;
  80.   else
  81.   {
  82.     int raznica = first_elem - 1;
  83.     index = poisk (raznica, 1, n);
  84.     middle = vvod (index);
  85.   }
  86.  
  87.   if (znach > middle)
  88.     k = -1;
  89.   else if (znach == first_elem)
  90.     k = 1;
  91.   else if (znach == last_elem)
  92.     k = n;
  93.   else if (index != n && znach < last_elem)
  94.     k = bin (znach, index+1, n);
  95.   else if (znach > first_elem)
  96.     k = bin (znach, 1, index);
  97.   else if (index == n && znach < last_elem && znach > first_elem)
  98.     k = bin (znach, 1, n);
  99.    
  100.  
  101.    cout << "!" << " " << k << endl;
  102.  
  103.    for (int i = 1; i< m; i++)
  104.    {
  105.      int znachenie;
  106.      cin >> znachenie;
  107.  
  108.      if (znachenie > middle)
  109.       k = -1;
  110.     else if (znachenie == first_elem)
  111.       k = 1;
  112.     else if (znachenie == last_elem)
  113.       k = n;
  114.     else if (index != n && znachenie < last_elem)
  115.       k = bin (znachenie, index+1, n);
  116.     else if (znachenie > first_elem)
  117.       k = bin (znachenie, 1, index);
  118.     else if (index == n && znach < last_elem && znach > first_elem)
  119.       k = bin (znachenie, 1, n);
  120.    
  121.     cout << "!" << " " << k << endl;
  122.    }
  123. }
RAW Paste Data