제출 #311702

#제출 시각아이디문제언어결과실행 시간메모리
311702semiauto커다란 상품 (IOI17_prize)C++11
93.99 / 100
60 ms5512 KiB
#include "prize.h" #include <bits/stdc++.h> using namespace std; int i,s=1,pos,l,r; vector <int> v[200001]; set <pair <int,int> > myset; int find_best(int n) { v[1]=ask(1); for (i=1;i<=475;i++) { v[i]=ask(i-1); if ((v[i][0]+v[i][1])==0) return i-1; if ((v[s][0]+v[s][1])<=(v[i][0]+v[i][1])) s=i; } myset.insert({v[s][0],s}); myset.insert({200001,n+1}); while (true){ pos=s; l=(*(--(myset.upper_bound({v[s][0],200001})))).second; r=(*(myset.upper_bound({v[s][0]+1,0}))).second; for (i=17;i>=0;i--) { if (pos+(1<<i)>=r) continue; pos+=(1<<i); if (pos<=l) continue; if (!(v[pos].size())) v[pos]=ask(pos-1); if ((v[pos][0]+v[pos][1])!=(v[s][0]+v[s][1])) { if ((v[pos][0]+v[pos][1])==0) return pos-1; pos-=(1<<i); continue; } myset.insert({v[pos][0],pos}); if (v[pos][0]>v[s][0]) pos-=(1<<i); } for (i=pos+1;i<=n;i++) { if (!(v[i].size())) v[i]=ask(i-1); if ((v[i][0]+v[i][1])==0) return i-1; if ((v[i][0]+v[i][1])==(v[s][0]+v[s][1])) break; } s=i; myset.insert({v[s][0],s}); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...