#include "prize.h" #include <bits/stdc++.h> using namespace std; vector<int> dp[200002]; bool done[200002][2]; int find_best(int n) { //memset(dp,-1,sizeof dp); int idx=(n-1)/2; for (int q = 50; q >=0 ; q--) { int l,r; vector<int> res; //if(!dp[idx].empty())res=dp[idx]; res=ask(idx); //cerr<<q<<"\n"; if(res[0]+res[1]==0)return idx; if(res[1]>=res[0])l=idx,r=n-1; else r=idx,l=0; idx=(l+r)/2; while(l<r){ //cerr<<l<<" "<<r<<"\n"; int med=(l+r)/2; res=ask(med); if(res[0]+res[1]==0)return med; //cerr<<med<<"\n"; if(done[med][1]){r=med-1,idx=r;continue;} if(done[med][0]){l=med+1,idx=l;continue;} if(res[1]>=res[0])done[med][1]=1,l=med+1,idx=l; else done[med][0]=1,r=med-1,idx=r; } } return 0; }