#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 level, lvcnt[5]; vector<int> tar, cand; void dfs(int l, int r, int cnt, int lp, int rs) { if (r - l + 1 == cnt) { for (int i = l; i <= r; i++) { tar.push_back(cand[i]); } } else { int rm = l + (r - l) / 2; vector<int> res = qry(cand[rm]); if (res[0] + res[1] == lvcnt[level]) { if (res[0] - lp > 0) { dfs(l, rm - 1, res[0] - lp, lp, res[1]); } if (res[1] - rs > 0) { dfs(rm + 1, r, res[1] - rs, res[0], rs); } } else { int lm = rm; while (res[0] + res[1] < lvcnt[level]) { tar.push_back(cand[lm]); lm--; if (lm < l) { break; } res = qry(cand[lm]); } if (lm >= l) { int lc = res[0] - lp; if (lc > 0) { dfs(l, lm - 1, lc, lp, res[1]); } int rc = res[1] - rs - (rm - lm); if (rc > 0) { dfs(rm + 1, r, rc, res[0] + (rm - lm), rs); } } else { int 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 lc = res[0] - lp - (lm - rm); if (lc > 0) { dfs(l, rm - 1, lc, lp, res[1] - (rm - 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 u = 0; while (true) { int t = u, sum = t * t + t + 1; while (t > 1) { t = sqrt(t); sum += t; } if (sum > cand.size()) { u--; break; } u++; } int lim = 1, t = u; while (t > 1) { lim += t; t = sqrt(t); } for (int i = 0; i < lim; 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); sort(tar.begin(), tar.end()); tar.resize(unique(tar.begin(), tar.end()) - tar.begin()); cand = tar; level++; } return cand[0]; }