#include <iostream> #include <vector> #include "prize.h" using namespace std; int tot; vector<int> Ans, res; int Solve(int l, int r, int k){ vector<int> rs; if (l == r) return 0; int mid = (l + r) / 2, C = 0; rs = ask(mid); if (rs[0] + rs[1] != tot){ C = Solve(l, mid, k) + 1; Ans.push_back(mid); C += Solve(mid+1, r, k - C); return C; } C = Solve(l, mid, k); C += Solve(mid+1, r, rs[1]); return C; } int find_best(int n){ srand(time(0)); for (int i=1;i<=20;i++){ int id = rand() % n; res = ask(id); tot = max(tot, res[0] + res[1]); } Solve(0, n, tot); for (int i : Ans){ res = ask(i); if (res[0] + res[1] == 0) return i; } return 0; }