Submission #534713

#TimeUsernameProblemLanguageResultExecution timeMemory
534713benson1029The Big Prize (IOI17_prize)C++14
0 / 100
98 ms508 KiB
#include "prize.h" #include<bits/stdc++.h> using namespace std; vector< pair<int,int> > v; int sum; int ans; void recur(int l, int r) { if(ans!=-1) return; if(l>r) return; int mid = (l+r)/2; for(int i=mid; i<=r; i++) { vector<int> tmp = ask(i); if(tmp[0]+tmp[1] > sum) { recur(l, mid-1); recur(i+1, r); return; } else { v.push_back({tmp[0]+tmp[1], i}); if(tmp[0]+tmp[1]==0) { ans=i; return; } } } for(int i=mid-1; i>=l; i--) { vector<int> tmp = ask(i); if(tmp[0]+tmp[1] > sum) { recur(l, i-1); return; } else { v.push_back({tmp[0]+tmp[1], i}); if(tmp[0]+tmp[1]==0) { ans=i; return; } } } } int find_best(int n) { if(n<=5000) { for(int i=0; i<n; i++) { vector<int> tmp = ask(i); if(tmp[0]+tmp[1]==0) return i; } } sum = 0; for(int tmp=sqrt(sqrt(n)); tmp>=2; tmp=sqrt(tmp)) { sum += tmp; } sum++; ans = -1; recur(0, n-1); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...