Submission #798217

#	Time	Username	Problem	Language	Result	Execution time	Memory
798217		HaroldVemeno	Hiring (IOI09_hiring)	C++17	53 / 100	232 ms	10780 KiB

hiring

#include <bits/stdc++.h>

#ifdef GUDEB
    #define D(x) cerr << #x << ": " << (x) << '\n';
    #define ifdeb if(true)
#else
    #define D(x) ;
    #define ifdeb if(false)
#endif

#define all(x) begin(x), end(x)

using namespace std;
using ull = unsigned long long;
using ll = long long;
// #define int ll;

struct Z {
    int c;
    int q;
};

int s;
ll zsi[4400000];
ll csi[4400000];

pair<ll, ll> fbz(ll m, int u, int ub, int ue) {
    if(ub == ue-1) return {0, 0};
    int um = (ub+ue)/2;
    if(csi[2*u] > m) return fbz(m, 2*u, ub, um);
    auto [rz, rc] = fbz(m-csi[2*u], 2*u+1, um, ue);
    return {rz + zsi[2*u], rc + csi[2*u]};
}

void solve() {
    int n;
    long long m;
    cin >> n >> m;
    vector<Z> zs(n);
    for(int i = 0; i < n; ++i) {
        cin >> zs[i].c;
        cin >> zs[i].q;
    }
    vector<int> bp(n);
    iota(all(bp), 0);
    sort(all(bp), [&zs](int ai, int bi){
        Z& a = zs[ai];
        Z& b = zs[bi];
        return 1ll*a.c*b.q < 1ll*b.c*a.q;
    });
    ll mz = 0;
    s = 1 << 20;
    int bi = 0;
    ll mcn = 0;
    ll mcd = 1;
    ll mcq = 0;
    for(int i = 0; i < n; ++i) {
        Z& z = zs[bp[i]];
        zsi[s+z.q] += 1;
        csi[s+z.q] += z.q;
        for(int j = (s + z.q)/2; j > 0; j /= 2) {
            zsi[j] = zsi[2*j] + zsi[2*j+1];
            csi[j] = csi[2*j] + csi[2*j+1];
        }
        auto [fz, fc] = fbz(m*z.q/z.c, 1, 0, s);
        ll fcn = fc * z.c;
        ll fcd = z.q;
        if(fz > mz) {
            mz = fz;
            mcn = fcn;
            mcd = fcd;
            mcq = fc;
            bi = i;
        } else if(fz == mz && fcn*mcd < mcn*fcd) {
            mcn = fcn;
            mcd = fcd;
            bi = i;
            mcq = fc;
        }
    }
    {
        ll g = gcd(mcd, mcn);
        mcd /= g;
        mcn /= g;
    }
    //if(mcd == 1) cout << mz << ' ' << mcn << '\n';
    //else cout << mz << ' ' << mcn << '/' << mcd << '\n';
    cout << mz << '\n';
    vector<int> is(bi+1);
    iota(all(is), 0);
    sort(all(is), [&zs, &bp](int ai, int bi){
        Z& a = zs[bp[ai]];
        Z& b = zs[bp[bi]];
        return a.q < b.q;
    });
    ll sq = 0;
    vector<int> con;
    D(mcq)
    for(int i = 0; sq < mcq; ++i) {
        D(sq)
        con.push_back(bp[is[i]]);
        sq += zs[bp[is[i]]].q;
    }
    sort(all(con));
    for(int a : con) cout << a+1 << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << setprecision(20);

    solve();
}

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