제출 #641382

#제출 시각아이디문제언어결과실행 시간메모리
641382ggoh커다란 상품 (IOI17_prize)C++14
97.96 / 100
56 ms1872 KiB
#include "prize.h" #include<bits/stdc++.h> using namespace std; #define sz(v) ((int)(v).size()) typedef long long lint; int a[200002][2],cnt[200002],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]; } if(p==q)return ; int lh=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]; } } if(a[lh][0]+a[lh][1]==maxa) { if(p!=lh) { if(a[lh][0]!=left)f(p,lh-1,left,a[lh][1]); } if(a[lh][1]-(h-lh)!=right)f(h+1,q,(h-lh)+a[lh][0],right); } else { int rh=h; 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(a[rh][0]+a[rh][1]==maxa) { if(q!=rh)if(a[rh][1]!=right)f(rh+1,q,a[rh][0],right); } else return ; } } 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; int m=0,sameM=0; for(int i=2;1+i+(i*i+1)<=n;i++) { m=max(m,1+i); sameM=max(sameM,i); } for(int i=2;1+i+(i*i+1)<=n;i++) { for(int j=i*i+1;1+i+j+1ll*j*j+1<=n;j++) { m=max(m,1+i+j); sameM=max(sameM,j); } } for(int i=2;1+i+(i*i+1)<=n;i++) { for(int j=i*i+1;1+i+j+1ll*j*j+1<=n;j++) { for(int k=j*j+1;1+i+j+k+1ll*k*k+1<=n;k++) { m=max(m,1+i+j+k); sameM=max(sameM,k); } } } int o=n/m; for(int i=0;m--;i+=o) { 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]); cnt[a[i][0]+a[i][1]]++; if(cnt[a[i][0]+a[i][1]]>sameM)break; } 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...