Submission #532745

#TimeUsernameProblemLanguageResultExecution timeMemory
532745__VariattoHiring (IOI09_hiring)C++17
79 / 100
1586 ms19120 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second #define ll long long const ll MAX=5e5+10, L=16; const ll MAXV=1e18+10; struct st{ ll i, s, q; }t[MAX]; ll n, w; int minipos; bool spr(ll x){ ll sum=0; multiset<ll>m; for(ll i=1; i<=x; i++) sum+=t[i].q, m.insert(t[i].q); long double mini=MAXV; bool udalo=false; for(ll i=x; i<=n; i++){ if(i>x){ auto it=m.end(); it--; if(*it>t[i].q){ sum-=*it, sum+=t[i].q; m.erase(it), m.insert(t[i].q); } } if(w*t[i].q>=sum*t[i].s){ if(mini>sum*t[i].s/t[i].q) mini=sum*t[i].s/t[i].q, minipos=i; udalo=true; } } return udalo; } ll bin(){ ll pocz=0, kon=n, sr, wyn=0; while(pocz<=kon){ sr=(pocz+kon)/2; if(spr(sr)) wyn=sr, pocz=sr+1; else kon=sr-1; } return wyn; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin>>n>>w; for(ll i=1; i<=n; i++){ cin>>t[i].s>>t[i].q; t[i].i=i; } sort(t+1, t+n+1, [](st a, st b){ ll la=a.s/__gcd(a.s, a.q), ma=a.q/__gcd(a.s, a.q); ll lb=b.s/__gcd(b.s, b.q), mb=b.q/__gcd(b.s, b.q); ll nla=la*mb, nlb=lb*ma; return nla<nlb; }); int x=bin(); cout<<x<<"\n"; multiset<pair<int,int>>m; for(int i=1; i<=minipos; i++) m.insert({t[i].q, t[i].i}); int ile=0; for(multiset<pair<int,int>>::iterator it=m.begin(); true; it++){ cout<<(*it).se<<"\n"; ile++; if(ile==x) break; } }
#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...