Submission #827769

#TimeUsernameProblemLanguageResultExecution timeMemory
827769QwertyPiColors (BOI20_colors)C++14
0 / 100
1 ms256 KiB
#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; return; } #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); shift[N] = max(shift[N], 1 - hist_min); } #else int N; cin >> N; solve(N); #endif }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...