Submission #866423

#TimeUsernameProblemLanguageResultExecution timeMemory
866423HuyQuang_re_ZeroHiring (IOI09_hiring)C++14
100 / 100
189 ms16336 KiB
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 1000005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
using namespace std;
struct pt { ll cnt,sum; };
pt operator + (pt a,pt b) { return { a.cnt+b.cnt,a.sum+b.sum }; }
struct worker { ll s,q,pos; } a[N];
ll n,i,w,u,res,top,bot;
struct Interval_Tree
{
    pt st[100005];
    void update(int id,int l,int r,int u)
    {
        if(u<l || u>r) return ;
        if(l==r) { st[id].cnt++; st[id].sum+=u; return ; }
        int mid=(l+r)>>1;
        update(id*2,l,mid,u); update(id*2+1,mid+1,r,u);
        st[id]=st[id*2]+st[id*2+1];
    }
    pt Find(int id,int l,int r,ll k)
    {
        if(l==r) return { min(k/l,st[id].cnt),l*min(k/l,st[id].cnt) };
        int mid=(l+r)>>1;
        if(k<st[id*2].sum) return Find(id*2,l,mid,k);
        return st[id*2]+Find(id*2+1,mid+1,r,k-st[id*2].sum);
    }
} IT;
int main()
{
 //  freopen("hiring.inp","r",stdin);
   // freopen("hiring.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>w;
    for(i=1;i<=n;i++) cin>>a[i].s>>a[i].q,a[i].pos=i;
    sort(a+1,a+n+1,[&](worker a,worker b){ return a.s*b.q<a.q*b.s; });
    for(i=1;i<=n;i++)
    {
        IT.update(1,1,20000,a[i].q);
        pt x=IT.Find(1,1,20000,w*a[i].q/a[i].s);
        if(res<x.cnt || (res==x.cnt && top*a[i].q>bot*a[i].s*x.sum))
        {
            res=x.cnt;
            top=a[i].s*x.sum; bot=a[i].q;
            u=i;
        }
    }
    cout<<res<<'\n';
    sort(a+1,a+u+1,[&](worker a,worker b){ return a.q<b.q; });
    for(i=1;i<=res;i++) cout<<a[i].pos<<'\n';
}
#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...