Submission #866422

#	Time	Username	Problem	Language	Result	Execution time	Memory
866422		HuyQuang_re_Zero	Hiring (IOI09_hiring)	C++14	3 / 100	179 ms	14980 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; };
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';
}

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:53:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   53 |         if(res<x.cnt || (res==x.cnt && top*a[i].q>bot*a[i].s*x.sum));
      |         ^~
hiring.cpp:54:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   54 |         {
      |         ^

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