#include "prize.h" #include <bits/stdc++.h> using namespace std; vector<vector<int>> buf; vector<int> qry(int x) { if (buf[x].empty()) { buf[x] = ask(x); } return buf[x]; } int find_best(int n) { buf.clear(), buf.resize(n); vector<int> cand; for (int i = 0; i < n; i++) { cand.push_back(i); } int lvl = 5; vector<int> s(6); 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 = sqrt(t); sum += t; } if (sum <= cand.size()) { l = m; } else { r = m; } } int lim = 1, t = l; while (t > 1) { lim += t; t = sqrt(t); } for (int i = 0; i < lim; i++) { vector<int> res = qry(cand[i]); s[lvl] = max(s[lvl], res[0] + res[1]); } vector<int> pidx; for (int i = 1; i <= s[lvl]; i++) { int l = -1, r = cand.size() - 1; while (l + 1 < r) { int rm = l + (r - l) / 2, lm = rm; vector<int> res = qry(cand[lm]); while (res[0] + res[1] != s[lvl]) { lm--; if (lm < 0) { break; } res = qry(cand[lm]); } if ((lm < 0 ? 0 : res[0]) + rm - lm < i) { l = rm; } else { r = rm; } } pidx.push_back(cand[r]); } cand = pidx; lvl--; } return cand[0]; }