Submission #699194

#TimeUsernameProblemLanguageResultExecution timeMemory
699194maomao90Colors (BOI20_colors)C++17
0 / 100
0 ms208 KiB
// Hallelujah, praise the one who set me free // Hallelujah, death has lost its grip on me // You have broken every chain, There's salvation in your name // Jesus Christ, my living hope #include <bits/stdc++.h> using namespace std; #define REP(i, s, e) for (int i = (s); i < (e); i++) #define RREP(i, s, e) for (int i = (s); i >= (e); i--) template <class T> inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;} template <class T> inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;} typedef long long ll; typedef long double ld; #define FI first #define SE second typedef pair<int, int> ii; typedef pair<ll, ll> pll; typedef tuple<int, int, int> iii; #define ALL(_a) _a.begin(), _a.end() #define SZ(_a) (int) _a.size() #define pb push_back typedef vector<int> vi; typedef vector<ll> vll; typedef vector<ii> vii; typedef vector<iii> viii; #ifndef DEBUG #define cerr if (0) cerr #endif const int INF = 1000000005; const ll LINF = 1000000000000000005ll; ll n; vll qry; inline bool ask(ll x) { cout << "? " << x << endl; bool r; cin >> r; return r; } int main() { cin >> n; ll lo = 1, hi = n, mid; while (lo < hi) { mid = lo + hi + 1 >> 1; cerr << ' ' << mid << '\n'; qry.pb(mid); lo = mid; } qry.pop_back(); ll lft = LINF, rht = -LINF; ll d = 0; REP (i, 0, SZ(qry)) { if (i & 1 ^ 1) { d -= qry[i]; } else { d += qry[i]; } mnto(lft, d); mxto(rht, d); } ll s = -lft + 1; assert(s + rht <= n); ask(s); lo = 1, hi = n; bool tog = 0; while (lo < hi) { mid = lo + hi + 1 >> 1; if (!tog) { s -= mid; } else { s += mid; } tog ^= 1; if (s < 1 || s > n) { break; } int res = ask(s); if (res) { lo = mid; } else { hi = mid - 1; } } assert(hi - lo <= 2); if (hi - lo == 2) { assert(hi == n); ask(1); if (ask(n)) { hi = n - 1; } else { hi = n; } } cout << "= " << hi << '\n'; return 0; }

Compilation message (stderr)

Colors.cpp: In function 'int main()':
Colors.cpp:50:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |         mid = lo + hi + 1 >> 1;
      |               ~~~~~~~~^~~
Colors.cpp:59:15: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   59 |         if (i & 1 ^ 1) {
      |             ~~^~~
Colors.cpp:73:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |         mid = lo + hi + 1 >> 1;
      |               ~~~~~~~~^~~
#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...