fork download
copy 
  1. /*
  2. ███████╗ █████╗ ██╗     ███╗   ███╗ █████╗           ██╗  ██╗ █████╗ ███╗   ██╗██╗
  3. ██╔════╝██╔══██╗██║     ████╗ ████║██╔══██╗          ██║  ██║██╔══██╗████╗  ██║██║
  4. ███████╗███████║██║     ██╔████╔██║███████║          ███████║███████║██╔██╗ ██║██║
  5. ╚════██║██╔══██║██║     ██║╚██╔╝██║██╔══██║          ██╔══██║██╔══██║██║╚██╗██║██║
  6. ███████║██║  ██║███████╗██║ ╚═╝ ██║██║  ██║ ███████╗ ██║  ██║██║  ██║██║ ╚████║██║
  7. ╚══════╝╚═╝  ╚═╝╚══════╝╚═╝     ╚═╝╚═╝  ╚═╝ ╚══════╝ ╚═╝  ╚═╝╚═╝  ╚═╝╚═╝  ╚═══╝╚═╝
  8. */
  9.  
  10. #include <bits/stdc++.h>
  11.  
  12. using namespace std;
  13. #define sp " "
  14. #define ll long long
  15. #define ld long double
  16. #define oo (ll)(1e16)
  17. #define OO (ll)(1e9)
  18. #define cin(vec) for(auto& i : vec) cin >> i;
  19. #define sz(s) (int)(s.size())
  20. #include<ext/pb_ds/assoc_container.hpp> // keep-include
  21. #include<ext/pb_ds/tree_policy.hpp> // keep-include
  22. using namespace __gnu_pbds;
  23. template <typename key>
  24. using ordered_set = tree<key, null_type, less_equal<key>, rb_tree_tag, tree_order_statistics_node_update>;
  25. //  find_by_order(k) :
  26. //  It returns to an iterator to the k-th element (counting from zero) in the set in O(logn) time.
  27. //  To find the first element k must be zero.
  28. //  order_of_key(k) :
  29. //  It returns to the number of items that are strictly smaller than our item k in O(logn) time.
  30. int ask(int l, int r)
  31. {
  32.     cout << "? " << l << sp << r << endl;
  33.     cout.flush();
  34.     int ret;
  35.     cin >> ret;
  36.     return ret;
  37. }
  38.  
  39.  
  40. void FAST()
  41. {
  42.     ios_base::sync_with_stdio(false);
  43.     cin.tie(NULL);
  44.     cout.tie(NULL);
  45. }
  46.  
  47. void solve()
  48. {
  49.     int n, t;
  50.     cin >> n >> t;
  51.     vector<int> pref(n + 1, -1);
  52.  
  53.     ordered_set<int> os;
  54.     while (t--)
  55.     {
  56.         int k;
  57.         cin >> k;
  58.  
  59.         int l = 1, r = n;
  60.         while (l <= r)
  61.         {
  62.             int md = (l + r) / 2;
  63.             int p = 0;
  64.             int s = os.order_of_key(md + 1);
  65.             if (pref[md] != -1)
  66.                 p = pref[md] + s;
  67.             else
  68.             {
  69.                 p = ask(1, md);
  70.                 pref[md] = p  - s;
  71.             }
  72.             int z = md - p;
  73.  
  74.             if (z >= k)r = md - 1;
  75.             else l = md + 1;
  76.         }
  77.         cout << "! " << l << endl;
  78.         cout.flush();
  79.         os.insert(l);
  80.     }
  81. }
  82.  
  83.  
  84. int32_t main()
  85. {
  86.     FAST();
  87.     int t = 1;
  88.     // cin>>t;
  89.     while (t--)
  90.     {
  91.         solve();
  92.     }
  93. }
  94.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/yk5aeq
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!