제출 #641347

#제출 시각아이디문제언어결과실행 시간메모리
641347ggoh커다란 상품 (IOI17_prize)C++14
0 / 100
97 ms1864 KiB
#include "prize.h" #include<bits/stdc++.h> using namespace std; #define sz(v) ((int)(v).size()) typedef long long lint; int a[200000][2],n; vector<int>ret; int maxa; void f(int p,int q,int left,int right) { int h=(p+q)/2; if(a[h][0]==-1) { ret=ask(h); a[h][0]=ret[0]; a[h][1]=ret[1]; } int lh=h,rh=h; while(lh>p && a[lh][0]+a[lh][1]!=maxa) { lh--; if(a[lh][0]==-1) { ret=ask(lh); a[lh][0]=ret[0]; a[lh][1]=ret[1]; } } while(rh<q && a[rh][0]+a[rh][1]!=maxa) { rh++; if(a[rh][0]==-1) { ret=ask(rh); a[rh][0]=ret[0]; a[rh][1]=ret[1]; } } if(p!=lh) { if(a[lh][0]!=left)f(p,lh-1,left,a[lh][1]); } if(q!=rh) { if(a[rh][1]!=right)f(rh+1,q,a[rh][0],right); } } int find_best(int N) { n=N; memset(a,-1,sizeof(a)); if(n<=5000) { for(int i=0;i<n;i++) { ret=ask(i); if(!ret[0] && !ret[1])return i; } } maxa=-1; for(int i=0;i<n;i+=10) { if(a[i][0]==-1) { ret=ask(i); a[i][0]=ret[0]; a[i][1]=ret[1]; } if(!a[i][0] && !a[i][1])return i; maxa=max(maxa,a[i][0]+a[i][1]); } if(a[n-1][0]==-1) { ret=ask(n-1); a[n-1][0]=ret[0]; a[n-1][1]=ret[1]; } if(!a[n-1][0] && !a[n-1][1])return n-1; maxa=max(maxa,a[n-1][0]+a[n-1][1]); f(0,n-1,0,0); for(int i=0;i<n;i++)if(!a[i][0] && !a[i][1])return i; return 0;//unreachable }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...