#include "prize.h" #include <bits/stdc++.h> using namespace std; vector<vector<int>> buf; vector<int> qry(int x) { if (buf[x].empty()) { return buf[x] = ask(x); } else { return buf[x]; } } int level, lvcnt[5]; vector<int> tar, cand; void dfs(int l, int r, int cnt, int lp, int rs) { 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) { auto getlim = [] (int n) { 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 <= n) { l = m; } else { r = m; } } double p = 1; int ret = 1; for (int i = 0; p >= 0.001 && i < cand.size(); i++, ret++) { p *= (double)(r - i) / (cand.size() - i); } if (p >= 0.001) { return r; } else { return ret; } }; int lim = getlim(cand.size()); 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]; }