제출 #406945

#제출 시각아이디문제언어결과실행 시간메모리
406945Peti커다란 상품 (IOI17_prize)C++14
20 / 100
107 ms328 KiB
#include <bits/stdc++.h> #include "prize.h" using namespace std; const int bont = 800; int find_best(int n) { int s = 460, ert = 0; for(int i = 0; i < min(n, 460); 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; } while(s+1 < e && ans[0] < ans2[0]){ 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...