Submission #866419

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
866419	2023-10-26T05:56:56 Z	HuyQuang_re_Zero	Hiring (IOI09_hiring)	C++14	74 / 100	196 ms	21588 KB

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.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2396 KB	Output is correct
2	Partially correct	0 ms	2396 KB	Partially correct
3	Partially correct	1 ms	2512 KB	Partially correct
4	Correct	1 ms	2392 KB	Output is correct
5	Correct	1 ms	2392 KB	Output is correct
6	Correct	1 ms	2648 KB	Output is correct
7	Partially correct	1 ms	2520 KB	Partially correct
8	Partially correct	2 ms	2652 KB	Partially correct
9	Correct	2 ms	2652 KB	Output is correct
10	Correct	2 ms	2720 KB	Output is correct
11	Partially correct	3 ms	2652 KB	Partially correct
12	Correct	3 ms	2652 KB	Output is correct
13	Partially correct	4 ms	2652 KB	Partially correct
14	Correct	6 ms	2652 KB	Output is correct
15	Partially correct	6 ms	2648 KB	Partially correct

Subtask #2
24.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Partially correct	1 ms	2396 KB	Partially correct
3	Correct	1 ms	2652 KB	Output is correct
4	Correct	8 ms	2776 KB	Output is correct
5	Correct	16 ms	5212 KB	Output is correct
6	Partially correct	133 ms	14572 KB	Partially correct
7	Correct	131 ms	17740 KB	Output is correct

Subtask #3
3.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	1 ms	2652 KB	Partially correct
2	Partially correct	1 ms	2652 KB	Partially correct
3	Correct	1 ms	2652 KB	Output is correct

Subtask #4
3.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	1 ms	2652 KB	Partially correct
2	Partially correct	1 ms	2652 KB	Partially correct
3	Correct	1 ms	2652 KB	Output is correct

Subtask #5
3.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	1 ms	2652 KB	Partially correct
2	Partially correct	1 ms	2652 KB	Partially correct
3	Correct	1 ms	2652 KB	Output is correct

Subtask #6
3.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	50 ms	5972 KB	Partially correct
2	Partially correct	47 ms	5928 KB	Partially correct
3	Correct	45 ms	5924 KB	Output is correct

Subtask #7
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	69 ms	9044 KB	Output is correct
2	Correct	63 ms	9044 KB	Output is correct
3	Correct	77 ms	9040 KB	Output is correct

Subtask #8
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	164 ms	18768 KB	Output is correct
2	Correct	168 ms	18812 KB	Output is correct
3	Correct	161 ms	18808 KB	Output is correct

Subtask #9
3.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	196 ms	21588 KB	Output is correct
2	Partially correct	187 ms	21564 KB	Partially correct
3	Correct	185 ms	21580 KB	Output is correct

Submission #866419

Compilation message