#include "prize.h" #include <bits/stdc++.h> using namespace std; vector<int> dp[200002]; bool check(int med,int idx){ vector<int> res; if(!dp[med].empty())res=dp[med]; else res=ask(med),dp[med]=res; if(dp[idx].empty())dp[idx]=ask(idx); return (dp[idx][0]==res[0]&&dp[idx][1]==res[1]); } int find_best(int n) { /*for (int i = 29979; i < 29979+sqrt(n); ++i) { cerr<<ask(i)[0]<<" "<<ask(i)[1]<<"\n"; }*/ int s=sqrt(n),l=0; int maxi=0,idx=0,last=idx; for (int i = 0; i < min(477,n); ++i) { dp[i]=ask(i); if(dp[i][0]+dp[i][1]==0)return i; if(dp[i][0]+dp[i][1]>=maxi)maxi=dp[i][0]+dp[i][1],idx=i; } for (int j = 477; j < n; j+=s) { //cerr<<j<<"a\n"; while(idx<(j+s-1)){ int l=idx+1,r=j+s-1,ans=idx; while(l<=r){ int med=(l+r)/2; if(check(med,idx))ans=med,l=med+1; else r=med-1; if(med<n&&dp[med][0]+dp[med][1]==0)return med; } ans++; while(ans<(j+s)){ vector<int> res; if(!dp[ans].empty())res=dp[ans]; else res=ask(ans),dp[ans]=res; if(dp[ans][0]+dp[ans][1]==0)return ans; if(dp[ans][0]+dp[ans][1]>=maxi){ maxi=dp[ans][0]+dp[ans][1],idx=ans; break; } ans++; } if(ans>=(j+s)){idx=j+s;} } for (int i = idx; i < min(j+s,n); i++) { //cerr<<i<<"\n"; dp[i]=ask(i); if(dp[i][0]+dp[i][1]==0)return i; if(dp[i][0]+dp[i][1]>=maxi){maxi=dp[i][0]+dp[i][1];idx=i;break;} } } //cerr<<last; for (int i = idx; i < n; ++i) { dp[i]=ask(i); if(dp[i][0]+dp[i][1]==0)return i; } return 0; }

prize.cpp: In function 'int find_best(int)':
prize.cpp:17:16: warning: unused variable 'l' [-Wunused-variable]
  int s=sqrt(n),l=0;
                ^
prize.cpp:18:19: warning: unused variable 'last' [-Wunused-variable]
  int maxi=0,idx=0,last=idx;
                   ^~~~