#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); if (res[0]+res[1] == 0) throw 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 is_trash(int i) { auto [ca, cb] = Ask(i); return ca+cb == lowest_rank; } bool weirdo[maxn]; void find_all_weirdos(int l, int r, int cnt, int bl, int br) { for (;;) { if (!cnt || l>r) return; if (vis[l]) { if (!is_trash(l)) { weirdo[l] = true; --cnt; ++bl; } ++l; continue; } if (vis[r]) { if (!is_trash(r)) { weirdo[r] = true; --cnt; ++br; } --r; continue; } break; } 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) { try { 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); int last_trash = -1, last_ca = 0; for (int i=0; i<n; ++i) if (vis[i]) { auto [ca, cb] = cache[i]; if (is_trash(i)) { if (last_ca == ca) { for (int j=last_trash+1; j<i; ++j) { vis[j] = true; cache[j] = cache[i]; } } else { find_all_weirdos(last_trash, i-1, ca-last_ca, last_ca, lowest_rank-ca); } last_trash = i; last_ca = ca; } } 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; } catch (int i) { return i; } }