#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(a) (a).begin(), (a).end()
long long C;
set<ll> st;
ll last = -1;
int _query = 0;
int ask(ll x){
_query++;
cout << "? " << x << endl;
// if(st.count(x)){
// cout << " Used before!" << endl;
// exit(0);
// }
// st.insert(x);
int res;
#ifdef LOCAL
res = (last == -1 || llabs(x - last) >= C ? 1 : 0);
#else
cin >> res;
#endif
last = x;
return res;
}
void out(ll x){
cout << "= " << x << endl;
#ifdef LOCAL
assert(x == C);
cout << _query << " queries called!";
#endif
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll n; cin >> n;
#ifdef LOCAL
cin >> C;
#endif
ll l = 0, r = n;
ll cur = 1;
vector<ll> q;
while(r - l > 1){
ll m = (l + r) / 2;
q.push_back(m);
l = m + 1;
}
reverse(all(q));
for(auto u : q){
if(cur + u <= n) cur += u;
else cur -= u;
}
ask(cur);
l = 0, r = n;
while(r - l > 1){
ll m = (l + r) / 2;
if(st.count(cur + m) || cur + m > n){
cur -= m;
}else cur += m;
if(ask(cur)){
r = m;
}else l = m;
}
out(r);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
OK (4 queries) |
| 2 |
Correct |
0 ms |
344 KB |
OK (7 queries) |
| 3 |
Correct |
1 ms |
344 KB |
OK (4 queries) |
| 4 |
Correct |
0 ms |
344 KB |
OK (5 queries) |
| 5 |
Correct |
0 ms |
344 KB |
OK (5 queries) |
| 6 |
Correct |
0 ms |
344 KB |
OK (7 queries) |
| 7 |
Correct |
0 ms |
344 KB |
OK (7 queries) |
| 8 |
Correct |
0 ms |
344 KB |
OK (6 queries) |
| 9 |
Correct |
0 ms |
344 KB |
OK (7 queries) |
| 10 |
Correct |
1 ms |
344 KB |
OK (4 queries) |
| 11 |
Correct |
0 ms |
344 KB |
OK (5 queries) |
| 12 |
Runtime error |
0 ms |
344 KB |
Execution killed with signal 13 |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
OK (4 queries) |
| 2 |
Correct |
0 ms |
344 KB |
OK (7 queries) |
| 3 |
Correct |
1 ms |
344 KB |
OK (4 queries) |
| 4 |
Correct |
0 ms |
344 KB |
OK (5 queries) |
| 5 |
Correct |
0 ms |
344 KB |
OK (5 queries) |
| 6 |
Correct |
0 ms |
344 KB |
OK (7 queries) |
| 7 |
Correct |
0 ms |
344 KB |
OK (7 queries) |
| 8 |
Correct |
0 ms |
344 KB |
OK (6 queries) |
| 9 |
Correct |
0 ms |
344 KB |
OK (7 queries) |
| 10 |
Correct |
1 ms |
344 KB |
OK (4 queries) |
| 11 |
Correct |
0 ms |
344 KB |
OK (5 queries) |
| 12 |
Runtime error |
0 ms |
344 KB |
Execution killed with signal 13 |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
OK (4 queries) |
| 2 |
Correct |
0 ms |
344 KB |
OK (7 queries) |
| 3 |
Correct |
1 ms |
344 KB |
OK (4 queries) |
| 4 |
Correct |
0 ms |
344 KB |
OK (5 queries) |
| 5 |
Correct |
0 ms |
344 KB |
OK (5 queries) |
| 6 |
Correct |
0 ms |
344 KB |
OK (7 queries) |
| 7 |
Correct |
0 ms |
344 KB |
OK (7 queries) |
| 8 |
Correct |
0 ms |
344 KB |
OK (6 queries) |
| 9 |
Correct |
0 ms |
344 KB |
OK (7 queries) |
| 10 |
Correct |
1 ms |
344 KB |
OK (4 queries) |
| 11 |
Correct |
0 ms |
344 KB |
OK (5 queries) |
| 12 |
Runtime error |
0 ms |
344 KB |
Execution killed with signal 13 |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
OK (4 queries) |
| 2 |
Correct |
0 ms |
344 KB |
OK (7 queries) |
| 3 |
Correct |
1 ms |
344 KB |
OK (4 queries) |
| 4 |
Correct |
0 ms |
344 KB |
OK (5 queries) |
| 5 |
Correct |
0 ms |
344 KB |
OK (5 queries) |
| 6 |
Correct |
0 ms |
344 KB |
OK (7 queries) |
| 7 |
Correct |
0 ms |
344 KB |
OK (7 queries) |
| 8 |
Correct |
0 ms |
344 KB |
OK (6 queries) |
| 9 |
Correct |
0 ms |
344 KB |
OK (7 queries) |
| 10 |
Correct |
1 ms |
344 KB |
OK (4 queries) |
| 11 |
Correct |
0 ms |
344 KB |
OK (5 queries) |
| 12 |
Runtime error |
0 ms |
344 KB |
Execution killed with signal 13 |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
OK (4 queries) |
| 2 |
Correct |
0 ms |
344 KB |
OK (7 queries) |
| 3 |
Correct |
1 ms |
344 KB |
OK (4 queries) |
| 4 |
Correct |
0 ms |
344 KB |
OK (5 queries) |
| 5 |
Correct |
0 ms |
344 KB |
OK (5 queries) |
| 6 |
Correct |
0 ms |
344 KB |
OK (7 queries) |
| 7 |
Correct |
0 ms |
344 KB |
OK (7 queries) |
| 8 |
Correct |
0 ms |
344 KB |
OK (6 queries) |
| 9 |
Correct |
0 ms |
344 KB |
OK (7 queries) |
| 10 |
Correct |
1 ms |
344 KB |
OK (4 queries) |
| 11 |
Correct |
0 ms |
344 KB |
OK (5 queries) |
| 12 |
Runtime error |
0 ms |
344 KB |
Execution killed with signal 13 |
| 13 |
Halted |
0 ms |
0 KB |
- |
