제출 #291868

#제출 시각아이디문제언어결과실행 시간메모리
291868amiratou커다란 상품 (IOI17_prize)C++14
90 / 100
112 ms6196 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) { srand(time(0)); N=0; vector<int> vec(n); for (int i = 0; i < n; ++i)vec[i]=i; random_shuffle(vec.begin(),vec.end()); for (int i = 0; i < min(712,(int)(vec.size())); ++i) { vector<int> Y=query(vec[i]); if(!(Y[0]+Y[1]))return vec[i]; else N=max(N,Y[0]+Y[1]); } int l=close_left(0,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...