제출 #291893

#제출 시각아이디문제언어결과실행 시간메모리
291893amiratou커다란 상품 (IOI17_prize)C++14
20 / 100
111 ms5368 KiB
#include "prize.h" #include <bits/stdc++.h> using namespace std; vector<int> h[200005]; int f=-1,N; vector<int> query(int idx){ if(!h[idx].empty())return h[idx]; return h[idx]=ask(idx); } int close_left(int l,int r){ while(l<=r){ vector<int> M=query(l); if((M[0]+M[1])==N)return l; else if(!(M[0]+M[1])){f=l;return -1;} l++; } return -1; } int close_right(int l,int r){ while(r>=l){ vector<int> M=query(r); if((M[0]+M[1])==N)return r; else if(!(M[0]+M[1])){f=r;return -1;} r--; } return -1; } void gimme(int l,int r){ if(f!=-1)return; if(l==r)return ; vector<int> G=query(l),G2=query(r); if(G2[0]==G[0])return; int med=(l+r)>>1,k; vector<int> M=query(med); if(!(M[0]+M[1])){f=med;return;} else if((M[0]+M[1])==N){ gimme(l,med); if(f!=-1)return; k=close_left(med+1,r); if(f!=-1)return; if(k!=-1)gimme(k,r); } else{ k=close_right(l,med-1); if(f!=-1)return; if(k!=-1)gimme(l,k); if(f!=-1)return; k=close_left(med+1,r); if(f!=-1)return; if(k!=-1)gimme(k,r); } } int find_best(int n) { N=0; for (int i = 0; i < min(448,n); ++i) { vector<int> Y=query(i); if(!(Y[0]+Y[1]))return i; else N=max(N,Y[0]+Y[1]); } int l=close_left(448,n-1); if(f!=-1)return f; assert(l!=-1); int r=close_right(l,n-1); if(f!=-1)return f; assert(r!=-1); gimme(l,r); assert(f!=-1); return f; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...