제출 #268129

#제출 시각아이디문제언어결과실행 시간메모리
268129Plurm커다란 상품 (IOI17_prize)C++11
0 / 100
89 ms5368 KiB
#include "prize.h" #include <bits/stdc++.h> using namespace std; vector<int> memoiz[200005]; vector<int> customAsk(int x){ // Memoized version of ask if(memoiz[x].empty()) return memoiz[x] = ask(x); else return memoiz[x]; } int solve(int l, int r, int offsL, int offsR){ if(l == r) return -1; int m = (l+r)/2; vector<int> res = customAsk(m); if(res[0] + res[1] == 0) return m; int left = -1; if(res[0] - offsL > 0) left = solve(l, m-1, offsL, res[1]); if(left != -1) return left; if(res[1] - offsR > 0) return solve(m+1, r, res[0], offsR); return -1; } int find_best(int n) { if(n < 5000){ for(int i = 0; i < n; i++) { vector<int> res = customAsk(i); if(res[0] + res[1] == 0) return i; } } int b = sqrt(n); vector<tuple<int,int,int,int> > eachBlock; // (L, R, offsL, offsR) int last = 0; int lidx = -1; for(int i = b; i < n;){ vector<int> cur = customAsk(i); if(cur[0] + cur[1] <= 2*b){ i++; }else{ eachBlock.emplace_back(lidx+1, i, last, cur[1]); last = cur[0]; lidx = i; i += b; } } if(lidx != n-1) eachBlock.emplace_back(lidx+1, n-1, last, 0); for(auto block : eachBlock){ int l,r,ofl,ofr; tie(l,r,ofl,ofr) = block; int ret = solve(l, r, ofl, ofr); if(ret != -1) return ret; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...