Submission #866419

#	Time	Username	Problem	Language	Result	Execution time	Memory
866419		HuyQuang_re_Zero	Hiring (IOI09_hiring)	C++14	74 / 100	196 ms	21588 KiB

hiring

#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; } res;
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;
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.cnt<x.cnt || (res.cnt==x.cnt && res.sum>x.sum))
        {
            res=x;
            u=i;
        }
    }
    cout<<res.cnt<<'\n';
    sort(a+1,a+u+1,[&](worker a,worker b){ return a.q<b.q; });
    for(i=1;i<=res.cnt;i++) cout<<a[i].pos<<'\n';
}

• Subtask 1: 23 / 30
• Subtask 2: 24 / 28
• Subtask 3: 3 / 6
• Subtask 4: 3 / 6
• Subtask 5: 3 / 6
• Subtask 6: 3 / 6
• Subtask 7: 6 / 6
• Subtask 8: 6 / 6
• Subtask 9: 3 / 6