#include "prize.h" #include <utility> using namespace std; using pp=pair<int,int>; const int maxn = int(2e5) + 10; pp cache[maxn]; bool vis[maxn]; pp Ask(int i) { if (vis[i]) return cache[i]; vis[i] = true; vector<int> res = ask(i); return cache[i] = {res[0], res[1]}; } int lowest_rank; int _get_lowest_rank(int n) { int mx = 0, step=n/500; for (int i=0; i<500; ++i) { auto [a, b] = Ask(i*step); mx = max(mx, a+b); } return mx; } bool weirdo[maxn]; void find_all_weirdos(int l, int r, int cnt, int bl, int br) { if (!cnt || l>r) return; if (r-l+1 == cnt) { for (int i=l; i<=r; ++i) weirdo[i] = true; return; } int md = (l+r)/2; for (int i=md; l<=i; --i) { auto [ca, cb] = Ask(i); if (ca+cb == lowest_rank) { find_all_weirdos(l, i-1, ca-bl, bl, lowest_rank-ca); break; } else { weirdo[i] = true; } } for (int i=md; i<=r; ++i) { auto [ca, cb] = Ask(i); if (ca+cb == lowest_rank) { find_all_weirdos(i+1, r, cb-br, lowest_rank-cb, br); break; } else { weirdo[i] = true; } } } int find_best(int n) { if (n <= 5000) { for (int i=0; i<n; ++i) { auto [a, b] = Ask(i); if (a+b == 0) return i; } return -1; } lowest_rank = _get_lowest_rank(n); find_all_weirdos(0, n-1, lowest_rank, 0, 0); for (int i=0; i<n; ++i) if (weirdo[i]) { auto [a, b] = Ask(i); if (a+b == 0) return i; } return -1; }