제출 #1313285

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313285		hectormedrano	Hiring (IOI09_hiring)	C++20	100 / 100	495 ms	56424 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 val){
    if(l==r){
        if(st[id].second <= val){return st[id];}
        else{return {0, 0};}
    }
    ll m = (l+r)/2;
    if(st[2*id].second <= val){
        return st[2*id] + query(m+1, r, 2*id+1, val-st[2*id].second);
    } else {
        return query(l, m, 2*id, val);
    }
}

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;}
        pair<ll, ll> mx = query(0, N+1, 1, T);
        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;}
    a.clear();
    a.resize(N+2, 0);
    for(ll i=N-1;i>A.k;i--){
        a[c[i].pos + 1] = c[i].q;
        update(0, N+1, 1, c[i].pos + 1, c[i].q);
    }
    cout<<c[A.k].ind+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 = a[i];
        if(x==0){continue;}
        S += x;
        if(S > T){break;}
        cout<<ori[i-1]+1<<endl;
    }
}

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