#include <bits/stdc++.h> #include "prize.h" using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int smax = 0; int ans = -1; void getans(int l, int r, int lval, int rval) { if (ans != -1) return; if (l > r) return; int mid = (l+r)/2; vector <int> vmid = ask(mid); if (vmid[0] + vmid[1] == 0) { ans = mid; return; } if (vmid[0] + vmid[1] == smax) { if (vmid[0] > lval) getans(l,mid-1, lval,vmid[1]); if (vmid[1] > rval) getans(mid+1,r, vmid[0],rval); return; } int curr = mid+1; int curl = mid-1; vector <int> resr,resl; bool okl = false; bool okr = false; while (curr <= r) { resr = ask(curr); if (resr[0] + resr[1] == 0) { ans = curr; return; } if (resr[0] + resr[1] == smax) { okr = true; break; } curr++; } while (curl >= l) { resl = ask(curl); if (resl[0] + resl[1] == 0) { ans = curl; return; } if (resl[0] + resl[1] == smax) { okl = true; break; } curl--; } if (okl) { if (resl[0] > lval) getans(l, curl-1,lval, resl[1]); } if (okr) { if (resr[1] > rval) getans(curr+1, r,resr[0], rval); } } int find_best(int n) { vector <int> res; for(int i = 0; i < 1; i++) { res = ask(i); smax = max(smax,res[0] + res[1]); if (smax >= 50) break; } if (smax == 0) return 0; getans(0,n-1,0,0); return ans; }