제출 #931392

#제출 시각아이디문제언어결과실행 시간메모리
931392qwushaColors (BOI20_colors)C++17
100 / 100
1 ms708 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define fi first #define se second typedef long double ld; const ll inf = 1e9; const ld eps = 1e-8; const ll logs = 32; #include <cmath> ll c(ll k) { cout << "? " << k << endl; ll x; cin >> x; return x; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ll n; cin >> n; ll lsz = 0, rsz = n; ll va = n / 2, lva; ll dif = n / 2; ll left = 0, right = 0; ll t = 1; while (dif > 1) { lva = va; va = (va + n) / 2; dif = va -lva; if (t) left += dif; else right += dif; t = 1 - t; } ll last; if (!t) last = left + 1; else last = n - (n / 2) - right; ll x = c(last); set<ll> st = {last}; while (rsz - lsz > 1) { ll sz = (rsz + lsz) / 2; ll ind; ll var1 = last + sz, var2 = last - sz; if (st.find(var1) != st.end() || var1 > n) ind = var2; else if (st.find(var2) != st.end() || var2 <= 0) ind = var1; else if (var2 > (n + 1 - var1)) ind = var2; else ind = var1; x = c(ind); st.insert(ind); if (x == 1) { rsz = sz; } else lsz = sz; last = ind; } cout << "= " << rsz << endl; }
#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...