Submission #1210934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210934		Hamed_Ghaffari	Hiring (IOI09_hiring)	C++20	53 / 100	348 ms	21264 KiB

hiring

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

using ll = long long;
using pii = pair<int, int>;
using pld = pair<ll, double>;

#define X first
#define Y second
#define mid ((l+r)>>1)
#define lc id<<1
#define rc lc|1

const int MXN = 5e5+5;

int n, S[MXN], Q[MXN], cnt[MXN<<2], sum[MXN<<2], ordq[MXN], posq[MXN], ordsq[MXN];
ll W;

void upd(int p, int l=1, int r=n+2, int id=1) {
    if(r-l == 1) {
        cnt[id] = 1;
        sum[id] = Q[ordq[l]];
        return;
    }
    p<mid ? upd(p, l, mid, lc) : upd(p, mid, r, rc);
    cnt[id] = cnt[lc] + cnt[rc];
    sum[id] = sum[lc] + sum[rc];
}

pld val;
int get(int i, int l=1, int r=n+2, int id=1) {
    if(r-l == 1) return l;
    if((1ll*(int(val.Y)+sum[lc])*S[i]+Q[i]-1)/Q[i]<=W) {
        val.X += cnt[lc];
        val.Y += sum[lc];
        return get(i, mid, r, rc);
    }
    return get(i, l, mid, lc);
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> W;
    for(int i=1; i<=n; i++) cin >> S[i] >> Q[i];
    iota(ordq+1, ordq+n+1, 1);
    sort(ordq+1, ordq+n+1, [&](int i, int j) {
        return Q[i] < Q[j];
    });
    for(int i=1; i<=n; i++) posq[ordq[i]] = i;
    iota(ordsq+1, ordsq+n+1, 1);
    sort(ordsq+1, ordsq+n+1, [&](int i, int j) {
        return S[i]*Q[j] < S[j]*Q[i];
    });
    pld ans = {0, 0};
    pii wh = {0, 0};
    for(int i=1; i<=n; i++) {
        upd(posq[ordsq[i]]);
        val = {0, 0};
        int r = get(ordsq[i]);
        val.Y = val.Y * double(S[ordsq[i]]) / double(Q[ordsq[i]]);
        if(val>ans) {
            ans = val;
            wh = {i, r};
        }
    }
    cout << ans.X << '\n';
    for(int i=1; i<=wh.X; i++)
        if(posq[ordsq[i]]<wh.Y)
            cout << ordsq[i] << '\n';
    return 0;
}

• Subtask 1: 18 / 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: 0 / 6
• Subtask 9: 0 / 6