Submission #574369

#TimeUsernameProblemLanguageResultExecution timeMemory
574369mosiashvililukaHiring (IOI09_hiring)C++14
50 / 100
205 ms15380 KiB
#include<bits/stdc++.h> using namespace std; long long a,b,c,d,e,i,j,ii,jj,zx,xc,W,seg[80009],seg2[80009],l,r,z,zz,za,L,pas1,pas2,pas3,I; pair <long long, long long> p[500009]; bool cmp(pair <long long, long long> q, pair <long long, long long> w){ if(q.first*w.second<=w.first*q.second) return 0; else return 1; } void read(long long q, long long w, long long rr){ if(q==w){ zx=L/q;zx=min(zx,seg2[rr]); z+=zx*q; zz+=zx; return; } if(seg[rr*2]>L){ read(q,(q+w)/2,rr*2); }else{ zz+=seg2[rr*2];z+=seg[rr*2]; L-=seg[rr*2]; read((q+w)/2+1,w,rr*2+1); } } void UP(long long rr, long long w){ if(rr==0) return; seg[rr]+=w;seg2[rr]++; UP(rr/2,w); } void upd(long long q, long long w){ UP(za+q-1,w); } int main(){ ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>a>>W; for(i=1; i<=a; i++){ cin>>p[i].first>>p[i].second; } za=1; while(za<20000) za*=2; sort(p+1,p+a+1,cmp); for(i=a; i>=1; i--){ z=0;zz=0; L=W*p[i].second/p[i].first;L-=p[i].second; if(L>=0) zz++; if(L>0) read(1,za,1); //cout<<i<<" "<<z<<" "<<zz<<"\n"; if(pas1<zz){ pas1=zz; zx=z+p[i].second; pas2=zx*p[i].first;pas3=p[i].second; I=i; }else{ if(pas1==zz){ zx=z+p[i].second; c=zx*p[i].first;d=p[i].second; if(c*pas3<pas2*d){ pas2=c;pas3=d; I=i; } } } upd(p[i].second,p[i].second); } cout<<pas1<<"\n"; for(i=1; i<=pas1; i++){ cout<<i<<"\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...