Submission #1313020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313020		hectormedrano	Hiring (IOI09_hiring)	C++20	42 / 100	1594 ms	55196 KiB

hiring

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct can{
    ll ind, q, s, pos;
};

struct ans{
    ll k, E;
    ll cw = 0;
};

vector<can> c;

bool operator <(ans x, ans y){
    if(x.cw != y.cw){return (x.cw < y.cw);}
    return ((c[y.k].q)*(c[x.k].s)*(x.E) > (c[x.k].q)*(c[y.k].s)*(y.E));
}

bool ord1(can x, can y){
    return (x.q < y.q);
}

bool ord2(can x, can y){
    return ((x.s)*(y.q) > (y.s)*(x.q));
}

vector<pair<ll, ll>> st;
vector<ll> a;

pair<ll, ll> operator +(pair<ll, ll> d1, pair<ll, ll> d2){
    return {d1.first + d2.first, d1.second + d2.second};
}

void build(ll l, ll r, ll id){
    if(l==r){st[id] = {0, a[l]}; return;}
    ll m = (l+r)/2;
    build(l, m, 2*id);
    build(m+1, r, 2*id+1);
    st[id] = st[2*id] + st[2*id+1];
}

void update(ll l, ll r, ll id, ll pos, ll val){
    if(l==r){
        st[id].first = 1;
        st[id].second = val;
        return;
    }
    ll m = (l+r)/2;
    if(pos<=m){update(l, m, 2*id, pos, val);}
    else{update(m+1, r, 2*id+1, pos, val);}
    st[id] = st[2*id] + st[2*id+1];
}

pair<ll, ll> query(ll l, ll r, ll id, ll ql, ll qr){
    if(r<ql or qr<l){return {0, 0};}
    if(ql<=l and r<=qr){return st[id];}
    ll m = (l+r)/2;
    return query(l, m, 2*id, ql, qr) + query(m+1, r, 2*id+1, ql, qr);
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    ll N, W;
    cin>>N>>W;
    vector<ll> ori(N);
    c.resize(N);
    st.resize(4*N+13);
    a.resize(N+2, 0);
    a[N+1] = 1e15;
    build(0, N+1, 1);
    for(ll i=0;i<N;i++){
        c[i].ind = i;
        cin>>c[i].s>>c[i].q;
    }
    sort(c.begin(), c.end(), ord1);
    for(ll i=0;i<N;i++){
        c[i].pos = i;
        ori[i] = c[i].ind;
    }
    sort(c.begin(), c.end(), ord2);
    ans A;
    for(ll i=N-1;i>=0;i--){
        ll T = (W*(c[i].q))/c[i].s - c[i].q;
        if(T < 0){continue;}
        ll bl = 0;
        ll br = N+1;
        while(br != bl+1){
            ll bm = (bl + br)/2;
            pair<ll, ll> d = query(0, N+1, 1, 0, bm);
            if(d.second <= T){bl = bm;}
            else{br = bm;}
        }
        pair<ll, ll> mx = query(0, N+1, 1, 0, bl);
        ans B;
        B.cw = mx.first + 1;
        B.E = mx.second + c[i].q;
        B.k = i;
        A = max(A, B);
        update(0, N+1, 1, c[i].pos + 1, c[i].q);
    }
    cout<<A.cw<<endl;
    if(A.cw == 0){return 0;}
    st.clear();
    st.resize(4*N+13, {0, 0});
    for(ll i=N-1;i>A.k;i--){
        update(0, N+1, 1, c[i].pos + 1, c[i].q);
    }
    cout<<A.k+1<<endl;
    ll T = (W*(c[A.k].q))/c[A.k].s;
    ll S = c[A.k].q;
    for(ll i=1;i<=N;i++){
        ll x = query(0, N+1, 1, i, i).second;
        if(x==0){continue;}
        S += x;
        if(S > T){break;}
        cout<<i<<endl;
    }
}

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