Submission #893970

#	Time	Username	Problem	Language	Result	Execution time	Memory
893970		abcvuitunggio	Hiring (IOI09_hiring)	C++17	60 / 100	228 ms	14492 KiB

hiring

#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;
pair <int, int> res;
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;
}
int get(int node, int l, int r, int val){
    if (l==r)
        return min(val/l,st[node].cnt);
    int mid=(l+r)>>1;
    return (st[node<<1].sum<val?st[node<<1].cnt+get(node<<1|1,mid+1,r,val-st[node<<1].sum):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)
            res=max(res,{get(1,1,20000,lim)+1,-j});
        update(1,1,20000,q[i]);
    }
    res.second=-res.second;
    cout << res.first << '\n';
    int j=a[res.second],lim=w*q[j]/s[j]-q[j];
    sort(a+1,a+res.second,[](int i, int j){return q[i]<q[j];});
    for (int i=1;i<res.second;i++){
        lim-=q[a[i]];
        if (lim<0)
            break;
        cout << a[i] << '\n';
    }
    cout << j << '\n';
}

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