Submission #406970

#TimeUsernameProblemLanguageResultExecution timeMemory
406970PetiThe Big Prize (IOI17_prize)C++14
94.22 / 100
65 ms328 KiB
#include <bits/stdc++.h> #include "prize.h" using namespace std; const int bont = 1200; int ert = 0; int megold(int l, int r, vector<int> ansl, vector<int> ansr){ if(l+1 >= r) return -1; //cout<<l<<" "<<r<<"\n"; int m1 = (l+r)/2; int m2 = m1; vector<int> ans = ask(m1); if(ans[0] + ans[1] == 0) return m1; vector<int> ans2 = ans; while(m1-1 > l && ans[0]+ans[1] != ert){ m1--; ans = ask(m1); if(ans[0] + ans[1] == 0) return m1; } while(m2+1 < r && ans2[0]+ans2[1] != ert){ m2++; ans2 = ask(m2); if(ans2[0] + ans2[1] == 0) return m2; } return max((ansl[0] < ans[0] ? megold(l, m1, ansl, ans) : -1), (ans2[0] < ansr[0] ? megold(m2, r, ans2, ansr) : -1)); } int find_best(int n) { int s = 500; for(int i = 0; i < min(n, 500); i++){ vector<int> ans = ask(i); if(ans[0]+ans[1] == 0) return i; ert = max(ert, ans[0]+ans[1]); } while(s < n){ vector<int> ans = ask(s); if(ans[0]+ans[1] == 0) return s; while(ans[0]+ans[1] != ert){ s++; ans = ask(s); if(ans[0]+ans[1] == 0) return s; } int e = min(s+bont, n-1); int s2 = e+1; vector<int> ans2 = ask(e); if(ans2[0]+ans2[1] == 0) return e; while(s < e && ans2[0]+ans2[1] != ert){ e--; ans2 = ask(e); if(ans2[0]+ans2[1] == 0) return e; } if(ans[0] < ans2[0]){ int temp = megold(s, e, ans, ans2); if(temp != -1) return temp; /*int l = s, r = e; while(l+1 < r){ int m = (l+r)/2; vector<int> ans3 = ask(m); if(ans3[0]+ans3[1] == 0) return m; if(ans3[0]+ans3[1] != ert || ans3[0] != ans[0]) r = m; else l = m; } s = l+2; ans = ask(s); if(ans[0]+ans[1] == 0) return s; while(s < e && ans[0]+ans[1] != ert){ s++; ans = ask(s); if(ans[0]+ans[1] == 0) return s; }*/ } s = s2; } return -1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...