Submission #981494

#TimeUsernameProblemLanguageResultExecution timeMemory
981494boyliguanhanThe Big Prize (IOI17_prize)C++17
100 / 100
31 ms2336 KiB
//viewed solution #include "prize.h" #include<bits/stdc++.h> using namespace std; int unloli,ans=-1; map<int,vector<int>> mem; vector<int>ask2(int n){ if(mem.count(n)) return mem[n]; return mem[n]=ask(n); } void calc(int l,int r,int tol,int tor){ if(ans>=0) return; if(l>r) return; if(tol+tor==unloli) return; if(tol+tor+r-l+1==unloli){ for(int i=l;i<=r;i++) { vector<int>x=ask2(i); if(x[0]+x[1]==0) { ans=i; return; } } return; } int mid=l+r>>1,pt=mid; vector<int>stuff=ask2(mid); if(stuff[0]+stuff[1]==0){ ans=mid; return; } while(stuff[0]+stuff[1]-unloli&&pt>l){ stuff=ask2(--pt); if(stuff[0]+stuff[1]==0){ ans=pt; return; } } if(stuff[0]+stuff[1]==unloli) calc(mid+1,r,stuff[0],tor), calc(l,pt-1,tol,stuff[1]); else { stuff=ask2(++mid); if(stuff[0]+stuff[1]==0) { ans=mid; return; } while(stuff[0]+stuff[1]-unloli){ stuff=ask2(++mid); if(stuff[0]+stuff[1]==0) { ans=mid; return; } } calc(mid+1,r,stuff[0],tor); } } int find_best(int n) { if(n<5002) { for(int i = 1; i < n; i++) { std::vector<int> res = ask2(i); if(res[0] + res[1] == 0) return i; } return 0; } map<int,int>cnt; int to=473; for(int i=0;i<to;i++){ vector<int>x=ask2(i); if(x[0]+x[1]==0) return i; cnt[x[0]+x[1]]++; unloli=max(unloli,x[0]+x[1]); if(unloli>27) to=i+1; } int s=0; for(auto[i,j]:cnt) s+=(i<unloli)*j; calc(to,n-1,s,0); return ans; }

Compilation message (stderr)

prize.cpp: In function 'void calc(int, int, int, int)':
prize.cpp:29:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     int mid=l+r>>1,pt=mid;
      |             ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...