Submission #778615

#TimeUsernameProblemLanguageResultExecution timeMemory
778615benjaminkleynThe Big Prize (IOI17_prize)C++17
0 / 100
63 ms684 KiB
#include "prize.h" #include <bits/stdc++.h> using namespace std; #define mp make_pair bool asked[200000]; int L[200000], R[200000]; int v, N; 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) { while (l < r && L[l] + R[l] != L[v] + R[v]) { l++; if (Ask(l)) return l; } while (l < r && L[r] + R[r] != R[v] + R[v]) { r--; if (Ask(r)) return r; } int m = (l + r) / 2; if (Ask(m)) return m; if (l == r) return -1; int x = Find(l, m); if (x >= 0) return x; int y = Find(m, r); if (y >= 0) return y; return -1; } int find_best(int n) { memset(asked, false, sizeof(asked)); N = n, v = 0; for (int j = 0; j < n && j < 474; j++) { if (Ask(j)) return j; if (L[j] + R[j] > L[v] + R[v]) v = j; } 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...