Submission #778636

#TimeUsernameProblemLanguageResultExecution timeMemory
778636benjaminkleynThe Big Prize (IOI17_prize)C++17
20 / 100
79 ms1788 KiB
#include "prize.h" #include <bits/stdc++.h> using namespace std; #define mp make_pair bool asked[200000] = {false}; int L[200000], R[200000]; bool Ask(int i) { if (asked[i]) return L[i] + R[i] == 0; asked[i] = true; vector<int> res = ask(i); L[i] = res[0], R[i] = res[1]; return L[i] + R[i] == 0; } int Find(int l, int r) { int m = (l + r) / 2; if (Ask(m)) return m; if (R[l] == R[r] && L[r] == L[l]) return -1; int x = Find(l, m); if (x >= 0) return x; if (Ask(m+1)) return m+1; int y = Find(m + 1, r); if (y >= 0) return y; return -1; } int find_best(int n) { if (Ask(0)) return 0; if (Ask(n-1)) return n-1; return Find(0, n - 1); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...