#include <bits/stdc++.h>
#define int long long
using namespace std;
int hist_min, hist_max;
#ifndef LOCAL
bool qry(int x){
cout << "? " << x << endl;
bool r; cin >> r;
return r;
}
void answer(int x){
cout << "= " << x << endl;
exit(0);
}
#else
const int INF = 1LL << 60;
int prv = -INF, N, C;
int shift[100];
bool qry(int x){
hist_min = min(hist_min, x);
hist_max = max(hist_max, x);
cout << "Q " << x << ' ' << N << endl;
assert(1 <= x && x <= N);
if(prv == -INF) { prv = x; return 0; }
bool res = abs(x - prv) >= C; prv = x;
return res;
}
void answer(int x){
assert(x == C);
}
#endif
bool fake_qry(int x){
hist_min = min(hist_min, x);
hist_max = max(hist_max, x);
return false;
}
void fake_answer(int x){
return;
}
void fake_solve(int N){
int lo = 1, hi = N;
int prv = 1; fake_qry(prv);
bool forward = true;
while(lo < hi){
int mid = (lo + hi - 1) / 2;
int nxt = forward ? prv + mid : prv - mid;
forward ^= true;
if(fake_qry(nxt)){
hi = mid;
}else{
lo = mid + 1;
}
prv = nxt;
}
fake_answer(lo);
}
void solve(int N){
fake_solve(N);
int lo = 1, hi = N;
int prv = 2 - hist_min; qry(prv);
bool forward = true;
while(lo != hi){
int mid = (lo + hi - 1) / 2;
int nxt = forward ? prv + mid : prv - mid;
forward ^= true;
if(qry(nxt)){
hi = mid;
}else{
lo = mid + 1;
}
prv = nxt;
}
answer(lo);
}
int32_t main(){
#ifdef LOCAL
random_device rd;
mt19937 rng(rd());
const int MX = 100;
for(int t = 0; t < 10000; t++){
hist_min = INF, hist_max = -INF;
N = rng() % MX + 1;
C = rng() % N + 1;
solve(N);
printf("%lld => (%lld %lld)\n", N, hist_min, hist_max);
shift[N] = max(shift[N], 1 - hist_min);
}
for(int i = 1; i <= MX; i++) printf("%lld => %lld\n", i, shift[i]);
#else
int N; cin >> N;
solve(N);
#endif
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
OK (4 queries) |
| 2 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 3 |
Correct |
0 ms |
208 KB |
OK (4 queries) |
| 4 |
Correct |
1 ms |
208 KB |
OK (5 queries) |
| 5 |
Correct |
1 ms |
208 KB |
OK (5 queries) |
| 6 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 7 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 8 |
Correct |
0 ms |
208 KB |
OK (6 queries) |
| 9 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 10 |
Correct |
0 ms |
208 KB |
OK (4 queries) |
| 11 |
Correct |
0 ms |
208 KB |
OK (5 queries) |
| 12 |
Correct |
1 ms |
208 KB |
OK (6 queries) |
| 13 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 14 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 15 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 16 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 17 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 18 |
Correct |
0 ms |
208 KB |
OK (6 queries) |
| 19 |
Correct |
0 ms |
208 KB |
OK (6 queries) |
| 20 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 21 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 22 |
Runtime error |
0 ms |
208 KB |
Execution killed with signal 13 |
| 23 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
OK (4 queries) |
| 2 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 3 |
Correct |
0 ms |
208 KB |
OK (4 queries) |
| 4 |
Correct |
1 ms |
208 KB |
OK (5 queries) |
| 5 |
Correct |
1 ms |
208 KB |
OK (5 queries) |
| 6 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 7 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 8 |
Correct |
0 ms |
208 KB |
OK (6 queries) |
| 9 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 10 |
Correct |
0 ms |
208 KB |
OK (4 queries) |
| 11 |
Correct |
0 ms |
208 KB |
OK (5 queries) |
| 12 |
Correct |
1 ms |
208 KB |
OK (6 queries) |
| 13 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 14 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 15 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 16 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 17 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 18 |
Correct |
0 ms |
208 KB |
OK (6 queries) |
| 19 |
Correct |
0 ms |
208 KB |
OK (6 queries) |
| 20 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 21 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 22 |
Runtime error |
0 ms |
208 KB |
Execution killed with signal 13 |
| 23 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
OK (4 queries) |
| 2 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 3 |
Correct |
0 ms |
208 KB |
OK (4 queries) |
| 4 |
Correct |
1 ms |
208 KB |
OK (5 queries) |
| 5 |
Correct |
1 ms |
208 KB |
OK (5 queries) |
| 6 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 7 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 8 |
Correct |
0 ms |
208 KB |
OK (6 queries) |
| 9 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 10 |
Correct |
0 ms |
208 KB |
OK (4 queries) |
| 11 |
Correct |
0 ms |
208 KB |
OK (5 queries) |
| 12 |
Correct |
1 ms |
208 KB |
OK (6 queries) |
| 13 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 14 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 15 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 16 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 17 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 18 |
Correct |
0 ms |
208 KB |
OK (6 queries) |
| 19 |
Correct |
0 ms |
208 KB |
OK (6 queries) |
| 20 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 21 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 22 |
Runtime error |
0 ms |
208 KB |
Execution killed with signal 13 |
| 23 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
OK (4 queries) |
| 2 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 3 |
Correct |
0 ms |
208 KB |
OK (4 queries) |
| 4 |
Correct |
1 ms |
208 KB |
OK (5 queries) |
| 5 |
Correct |
1 ms |
208 KB |
OK (5 queries) |
| 6 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 7 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 8 |
Correct |
0 ms |
208 KB |
OK (6 queries) |
| 9 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 10 |
Correct |
0 ms |
208 KB |
OK (4 queries) |
| 11 |
Correct |
0 ms |
208 KB |
OK (5 queries) |
| 12 |
Correct |
1 ms |
208 KB |
OK (6 queries) |
| 13 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 14 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 15 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 16 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 17 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 18 |
Correct |
0 ms |
208 KB |
OK (6 queries) |
| 19 |
Correct |
0 ms |
208 KB |
OK (6 queries) |
| 20 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 21 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 22 |
Runtime error |
0 ms |
208 KB |
Execution killed with signal 13 |
| 23 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
OK (4 queries) |
| 2 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 3 |
Correct |
0 ms |
208 KB |
OK (4 queries) |
| 4 |
Correct |
1 ms |
208 KB |
OK (5 queries) |
| 5 |
Correct |
1 ms |
208 KB |
OK (5 queries) |
| 6 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 7 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 8 |
Correct |
0 ms |
208 KB |
OK (6 queries) |
| 9 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 10 |
Correct |
0 ms |
208 KB |
OK (4 queries) |
| 11 |
Correct |
0 ms |
208 KB |
OK (5 queries) |
| 12 |
Correct |
1 ms |
208 KB |
OK (6 queries) |
| 13 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 14 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 15 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 16 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 17 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 18 |
Correct |
0 ms |
208 KB |
OK (6 queries) |
| 19 |
Correct |
0 ms |
208 KB |
OK (6 queries) |
| 20 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 21 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 22 |
Runtime error |
0 ms |
208 KB |
Execution killed with signal 13 |
| 23 |
Halted |
0 ms |
0 KB |
- |
