fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. struct Seg {
  6.     int l, r;
  7.     ll sum;
  8.     int len() const { return r - l + 1; }
  9. };
  10.  
  11. int main() {
  12.     ios::sync_with_stdio(false);
  13.     cin.tie(nullptr);
  14.  
  15.     int T;
  16.     cin >> T;
  17.     while (T--) {
  18.         int n;
  19.         cin >> n;
  20.  
  21.         auto ask = [&](int l, int r) -> ll {
  22.             cout << "? " << l << " " << r << "\n" << flush;
  23.             ll res;
  24.             if (!(cin >> res)) exit(0);
  25.             if (res == -1) exit(0);
  26.             return res;
  27.         };
  28.  
  29.         unordered_map<int, ll> pref;
  30.         auto get_pref = [&](int pos) -> ll {
  31.             if (pos <= 0) return 0;
  32.             auto it = pref.find(pos);
  33.             if (it != pref.end()) return it->second;
  34.             ll val = ask(1, pos);
  35.             pref[pos] = val;
  36.             return val;
  37.         };
  38.  
  39.         auto range_sum = [&](int l, int r) -> ll {
  40.             return get_pref(r) - get_pref(l - 1);
  41.         };
  42.  
  43.         ll total = ask(1, n);
  44.  
  45.         auto cmp = [](const Seg& a, const Seg& b) {
  46.             return a.len() > b.len();
  47.         };
  48.         priority_queue<Seg, vector<Seg>, decltype(cmp)> pq(cmp);
  49.         pq.push({1, n, total});
  50.  
  51.         int Lmin = -1;
  52.         ll x = -1;
  53.  
  54.         while (!pq.empty()) {
  55.             Seg cur = pq.top(); pq.pop();
  56.             if (cur.len() == 1) {
  57.                 Lmin = 1;
  58.                 x = cur.sum;
  59.                 break;
  60.             }
  61.             if (cur.sum % 2 == 1) {
  62.                 Lmin = cur.len();
  63.                 x = cur.sum;
  64.                 break;
  65.             }
  66.             ll half = cur.sum / 2;
  67.             int L = cur.l, R = cur.r;
  68.             while (L < R) {
  69.                 int mid = (L + R) >> 1;
  70.                 ll s = range_sum(cur.l, mid);
  71.                 if (s >= half) R = mid;
  72.                 else L = mid + 1;
  73.             }
  74.             if (range_sum(cur.l, L) != half) {
  75.                 Lmin = cur.len();
  76.                 x = cur.sum;
  77.                 break;
  78.             } else {
  79.                 pq.push({cur.l, L, half});
  80.                 pq.push({L + 1, cur.r, half});
  81.             }
  82.         }
  83.  
  84.         int t = 63 - __builtin_clzll((ll)Lmin);
  85.         ll ans = x >> t;
  86.  
  87.         cout << "! " << ans << "\n" << flush;
  88.     }
  89.     return 0;
  90. }
  91.  
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
4
11
9
4
12
1
1
8
4
4
4
4
8
stdout
copy 
? 1 11
! 1
? 1 4
? 1 2
? 1 3
? 1 4
! 3
? 1 4
? 1 2
? 1 1
! 1
? 1 8
https://ideone.com/EJsFYc
language:
C++14 (gcc 8.3)
created:
6 days 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!