oj.uz

Submission #893974

# Submission time Handle Problem Language Result Execution time Memory
893974 2023-12-27T18:08:59 Z abcvuitunggio Hiring (IOI09_hiring) C++17
91 / 100
 245 ms 14444 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct T{
    int sum,cnt;
}st[80001];
int n,s[500001],q[500001],a[500001],w,res,num,den,pos;
void update(int node, int l, int r, int i){
    if (l>i||r<i)
        return;
    if (l==r){
        st[node].sum+=l;
        st[node].cnt++;
        return;
    }
    int mid=(l+r)>>1;
    update(node<<1,l,mid,i);
    update(node<<1|1,mid+1,r,i);
    st[node].sum=st[node<<1].sum+st[node<<1|1].sum;
    st[node].cnt=st[node<<1].cnt+st[node<<1|1].cnt;
}
pair <int, int> get(int node, int l, int r, int val){
    if (l==r){
        int x=min(val/l,st[node].cnt);
        return {x,l*x};
    }
    int mid=(l+r)>>1;
    if (st[node<<1].sum<val){
        auto [x,y]=get(node<<1|1,mid+1,r,val-st[node<<1].sum);
        x+=st[node<<1].cnt;
        y+=st[node<<1].sum;
        return {x,y};
    }
    return get(node<<1,l,mid,val);
}
int32_t main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> w;
    for (int i=1;i<=n;i++)
        cin >> s[i] >> q[i];
    iota(a,a+n+1,0);
    sort(a+1,a+n+1,[](int i, int j){return s[i]*q[j]<s[j]*q[i];});
    for (int j=1;j<=n;j++){
        int i=a[j];
        int lim=w*q[i]/s[i]-q[i];
        if (lim>=0){
            auto [x,y]=get(1,1,20000,lim);
            x++;
            y*=s[i];
            if (res<x||(res==x&&y*den<num*q[i])){
                res=x;
                num=y;
                den=q[i];
                pos=j;
            }
        }
        update(1,1,20000,q[i]);
    }
    cout << res << '\n';
    int j=a[pos],lim=w*q[j]/s[j]-q[j];
    sort(a+1,a+pos,[](int i, int j){return q[i]<q[j];});
    for (int i=1;i<pos;i++){
        lim-=q[a[i]];
        if (lim<0)
            break;
        cout << a[i] << '\n';
    }
    cout << j << '\n';
}

Subtask #1
26.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 6492 KB Partially correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Partially correct 1 ms 6492 KB Partially correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Partially correct 2 ms 6492 KB Partially correct
9 Correct 4 ms 6880 KB Output is correct
10 Correct 3 ms 6748 KB Output is correct
11 Partially correct 4 ms 6748 KB Partially correct
12 Correct 3 ms 6492 KB Output is correct
13 Correct 4 ms 6748 KB Output is correct
14 Correct 6 ms 7004 KB Output is correct
15 Correct 7 ms 7004 KB Output is correct

Subtask #2
26.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Partially correct 1 ms 6492 KB Partially correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 9 ms 7056 KB Output is correct
5 Correct 20 ms 10844 KB Output is correct
6 Correct 141 ms 13784 KB Output is correct
7 Correct 159 ms 13988 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 56 ms 13440 KB Partially correct
2 Partially correct 53 ms 13304 KB Partially correct
3 Correct 52 ms 13396 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 13648 KB Output is correct
2 Correct 76 ms 13480 KB Output is correct
3 Correct 76 ms 13648 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 14288 KB Output is correct
2 Correct 194 ms 14228 KB Output is correct
3 Correct 201 ms 14236 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 14444 KB Output is correct
2 Correct 245 ms 14372 KB Output is correct
3 Correct 220 ms 14416 KB Output is correct