제출 #593750

#제출 시각아이디문제언어결과실행 시간메모리
593750yutabi커다란 상품 (IOI17_prize)C++14
20 / 100
85 ms404 KiB
#include "prize.h" #include <bits/stdc++.h> using namespace std; #define pb push_back vector <bool> arr1_bad(200007,0); vector <bool> arr2_bad(500,1); int N; int heavy1; int heavy2; int query1(int loc) { int l=0; int r=N-1; int m=(l+r)/2; int left=0; while(l!=r) { while(arr1_bad[m]==1 && m>l) { m--; } if(m==l && arr1_bad[m]==1) { m=(l+r)/2; if(left+m-l+1<=loc) { return l+loc-left-1; } left+=m-l+1; l=m+1; m=(l+r)/2; continue; } vector <int> res=ask(m); if(res[0]+res[1]<heavy1) { arr1_bad[m]=1; continue; } if(res[0]<loc) { l=m+1; left=res[0]; } else { r=m; } m=(l+r)/2; } return l; } int query2(int loc) { int l=0; int r=heavy1-1; int m=(l+r)/2; int left=0; while(l!=r) { while(arr2_bad[m]==1 && m>l) { m--; } if(m==l && arr2_bad[m]==1) { m=(l+r)/2; if(left+m-l+1<=loc) { return l+loc-left-1; } left+=m-l+1; l=m+1; m=(l+r)/2; continue; } vector <int> res=ask(query1(m)); if(res[0]+res[1]<heavy2) { arr2_bad[m]=1; continue; } if(res[0]<loc) { l=m+1; left=res[0]; } else { r=m; } m=(l+r)/2; } return l; } int find_best(int n) { N=n; for(int i=0;i<min(500,n);i++) { vector <int> res=ask(i); heavy1=max(heavy1,res[0]+res[1]); } if(heavy1==1) { int l=0; int r=n-1; int m=(l+r)/2; while(l!=r) { vector <int> res=ask(m); if(res[1]==0) { r=m; } else { l=m+1; } m=(l+r)/2; } return m; } for(int i=0;i<min(25,heavy1);i++) { vector <int> res=ask(query1(i)); heavy2=max(heavy2,res[0]+res[1]); } for(int i=0;1;i++) { vector <int> res=ask(query1(query2(i))); if(res[0]+res[1]==0) { return query1(query2(i)); } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...