제출 #593163

#제출 시각아이디문제언어결과실행 시간메모리
593163Bench0310Hiring (IOI09_hiring)C++17
100 / 100
438 ms34136 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=500005; ll sum[4*N]; int cnt[4*N]; int s[N]; int q[N]; array<int,2> ord[N]; int h[N]; int qord[N]; array<int,2> opt[N]; void update(int idx,int l,int r,int pos,ll x,int y) { sum[idx]+=x; cnt[idx]+=y; if(l<r) { int m=(l+r)/2; if(pos<=m) update(2*idx,l,m,pos,x,y); else update(2*idx+1,m+1,r,pos,x,y); } } array<ll,2> descend(int idx,int l,int r,ll lim) { if(sum[idx]<=lim) return {sum[idx],cnt[idx]}; if(l==r) return {0,0}; int m=(l+r)/2; if(sum[2*idx]>lim) return descend(2*idx,l,m,lim); else { array<ll,2> t=descend(2*idx+1,m+1,r,lim-sum[2*idx]); return {sum[2*idx]+t[0],cnt[2*idx]+t[1]}; } } bool cmp(array<ll,2> a,array<ll,2> b){return (a[0]*b[1]<a[1]*b[0]);} int main() { ios::sync_with_stdio(0); cin.tie(0); int n; ll w; cin >> n >> w; for(int i=1;i<=n;i++) { cin >> s[i] >> q[i]; ord[i]={q[i],i}; } sort(ord+1,ord+n+1); for(int i=1;i<=n;i++) h[ord[i][1]]=i; for(int i=1;i<=n;i++) qord[i]=i; sort(qord+1,qord+n+1,[&](int x,int y){return cmp({s[x],q[x]},{s[y],q[y]});}); int rescnt=0; array<ll,2> rescost={0,1}; int respos=0; for(int i=1;i<=n;i++) { int x=qord[i]; update(1,1,n,h[x],q[x],1); auto [b,c]=descend(1,1,n,w*q[x]/s[x]); if(c>rescnt||(c==rescnt&&cmp({b*s[x],q[x]},rescost))) { rescnt=c; rescost={b*s[x],q[x]}; respos=i; } } for(int i=1;i<=respos;i++) { int x=qord[i]; opt[i]={q[x],x}; } sort(opt+1,opt+respos+1); cout << rescnt << "\n"; for(int i=1;i<=rescnt;i++) cout << opt[i][1] << "\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...