#include "prize.h" #include <bits/stdc++.h> using namespace std; int ans = -1; vector<vector<int>> buf; vector<int> qry(int x) { if (buf[x].empty()) { buf[x] = ask(x); } if (buf[x][0] + buf[x][1] == 0) { ans = x; } return buf[x]; } int level, lvcnt[5]; vector<int> tar, cand; void dfs(int l, int r, int cnt, int lp, int rs) { if (ans != -1) { return; } if (l == r) { tar.push_back(cand[l]); } else { int rm = l + (r - l) / 2, lm = rm; vector<int> res = qry(cand[lm]); while (res[0] + res[1] < lvcnt[level]) { tar.push_back(cand[lm]); lm--; if (lm < l) { break; } res = qry(cand[lm]); } int lc = res[0] - lp; if (lc > 0) { dfs(l, lm - 1, lc, lp, res[1]); } lm = rm; res = qry(cand[lm]); while (res[0] + res[1] < lvcnt[level]) { tar.push_back(cand[lm]); lm++; if (lm > r) { break; } res = qry(cand[lm]); } int rc = res[1] - rs; if (rc > 0) { dfs(lm + 1, r, rc, res[0], rs); } } } int find_best(int n) { buf.clear(), buf.resize(n); for (int i = 0; i < n; i++) { cand.push_back(i); } while (cand.size() > 1) { int l = 0, r = 500; while (l + 1 < r) { int m = l + (r - l) / 2; int t = m, sum = t * t + 1 + t; while (t > 1) { t = int(sqrt(t)); sum += t; } if (sum <= cand.size()) { l = m; } else { r = m; } } for (int i = 0; i < r; i++) { vector<int> res = qry(cand[i]); lvcnt[level] = max(lvcnt[level], res[0] + res[1]); } tar.clear(); dfs(0, cand.size() - 1, lvcnt[level], 0, 0); if (ans != -1) { return ans; } sort(tar.begin(), tar.end()); tar.resize(unique(tar.begin(), tar.end()) - tar.begin()); cand = tar; level++; } return cand[0]; }