oj.uz

Submission #593163

# Submission time Handle Problem Language Result Execution time Memory
593163 2022-07-10T14:03:20 Z Bench0310 Hiring (IOI09_hiring) C++17
100 / 100
 438 ms 34136 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N=500005;
ll sum[4*N];
int cnt[4*N];
int s[N];
int q[N];
array<int,2> ord[N];
int h[N];
int qord[N];
array<int,2> opt[N];

void update(int idx,int l,int r,int pos,ll x,int y)
{
    sum[idx]+=x;
    cnt[idx]+=y;
    if(l<r)
    {
        int m=(l+r)/2;
        if(pos<=m) update(2*idx,l,m,pos,x,y);
        else update(2*idx+1,m+1,r,pos,x,y);
    }
}

array<ll,2> descend(int idx,int l,int r,ll lim)
{
    if(sum[idx]<=lim) return {sum[idx],cnt[idx]};
    if(l==r) return {0,0};
    int m=(l+r)/2;
    if(sum[2*idx]>lim) return descend(2*idx,l,m,lim);
    else
    {
        array<ll,2> t=descend(2*idx+1,m+1,r,lim-sum[2*idx]);
        return {sum[2*idx]+t[0],cnt[2*idx]+t[1]};
    }
}

bool cmp(array<ll,2> a,array<ll,2> b){return (a[0]*b[1]<a[1]*b[0]);}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    ll w;
    cin >> n >> w;
    for(int i=1;i<=n;i++)
    {
        cin >> s[i] >> q[i];
        ord[i]={q[i],i};
    }
    sort(ord+1,ord+n+1);
    for(int i=1;i<=n;i++) h[ord[i][1]]=i;
    for(int i=1;i<=n;i++) qord[i]=i;
    sort(qord+1,qord+n+1,[&](int x,int y){return cmp({s[x],q[x]},{s[y],q[y]});});
    int rescnt=0;
    array<ll,2> rescost={0,1};
    int respos=0;
    for(int i=1;i<=n;i++)
    {
        int x=qord[i];
        update(1,1,n,h[x],q[x],1);
        auto [b,c]=descend(1,1,n,w*q[x]/s[x]);
        if(c>rescnt||(c==rescnt&&cmp({b*s[x],q[x]},rescost)))
        {
            rescnt=c;
            rescost={b*s[x],q[x]};
            respos=i;
        }
    }
    for(int i=1;i<=respos;i++)
    {
        int x=qord[i];
        opt[i]={q[x],x};
    }
    sort(opt+1,opt+respos+1);
    cout << rescnt << "\n";
    for(int i=1;i<=rescnt;i++) cout << opt[i][1] << "\n";
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Correct 5 ms 852 KB Output is correct
13 Correct 5 ms 980 KB Output is correct
14 Correct 7 ms 1236 KB Output is correct
15 Correct 8 ms 1236 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 11 ms 1820 KB Output is correct
5 Correct 33 ms 5712 KB Output is correct
6 Correct 228 ms 25108 KB Output is correct
7 Correct 307 ms 29540 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 8264 KB Output is correct
2 Correct 85 ms 8180 KB Output is correct
3 Correct 79 ms 8268 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 15036 KB Output is correct
2 Correct 132 ms 14984 KB Output is correct
3 Correct 132 ms 14960 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 31764 KB Output is correct
2 Correct 357 ms 31692 KB Output is correct
3 Correct 347 ms 31768 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 34136 KB Output is correct
2 Correct 405 ms 34108 KB Output is correct
3 Correct 433 ms 34116 KB Output is correct