제출 #73297

#제출 시각아이디문제언어결과실행 시간메모리
73297mr_banana커다란 상품 (IOI17_prize)C++17
0 / 100
9 ms644 KiB
#include "prize.h" #include <bits/stdc++.h> using namespace std; const int MN=200000+10,SQ=500; bool mark[MN]; int a[2][MN]; void get(int x){ if(mark[x]){ return; } mark[x]=1; auto v=ask(x); a[0][x]=v[0],a[1][x]=v[1]; } int numb(int x){ return a[0][x]+a[1][x]; } int numx; void fnd(int l,int r,int ls,int mr){ int num=numx-ls-mr; if(num==0){ return; } if(r-l<1){ return; } if(r-l<=num){ for(int i=l;i<r;i++){ get(i); } return; } int mid=(l+r)/2; while(true){ get(mid); if(numb(mid)<numx){ mid++; } else{ break; } } int mid1=(l+r)/2; if(mid==r){ fnd(l,mid1,ls,mr+mid-mid1); } else{ fnd(l,mid1,ls,a[1][mid]+mid-mid1); fnd(mid+1,r,a[0][mid],mr); } } int find_best(int n) { int mi=0; for(int i=0;i<SQ && i<n;i++){ get(i); if(numb(i)>numb(mi)){ mi=i; } } numx=numb(mi); fnd(0,n,0,0); for(int i=0;i<n;i++){ if(mark[i] && a[0][i]+a[1][i]==0){ return i; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...