제출 #1325741

#제출 시각아이디문제언어결과실행 시간메모리
1325741kasamchiHiring (IOI09_hiring)C++20
100 / 100
216 ms10880 KiB
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int cnt;
    long long sum;
    Node(void) : cnt(0), sum(0) {};
};

#define L(x) ((x) + (x))
#define R(x) (L(x) + 1)

Node SEG[100001];

void mod(int p, int ll, int rr, int id) {
    if (ll == p && rr == p) {
        SEG[id].cnt++, SEG[id].sum += p;
    } else {
        int mm = ll + (rr - ll) / 2;
        if (p <= mm) {
            mod(p, ll, mm, L(id));
        } else {
            mod(p, mm + 1, rr, R(id));
        }
        SEG[id].cnt = SEG[L(id)].cnt + SEG[R(id)].cnt;
        SEG[id].sum = SEG[L(id)].sum + SEG[R(id)].sum;
    }
}

void qry(long long lim, int ll, int rr, int id, int &cur, long long &sum) {
    if (ll == rr) {
        int cc = min((long long)SEG[id].cnt, lim / ll);
        cur += cc, sum += (long long)cc * ll;
    } else {
        int mm = ll + (rr - ll) / 2;
        if (SEG[L(id)].sum >= lim) {
            qry(lim, ll, mm, L(id), cur, sum);
        } else {
            cur += SEG[L(id)].cnt;
            sum += SEG[L(id)].sum;
            qry(lim - SEG[L(id)].sum, mm + 1, rr, R(id), cur, sum);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N;
    long long W;
    cin >> N >> W;

    vector<int> S(N), Q(N);
    for (int i = 0; i < N; i++) {
        cin >> S[i] >> Q[i];
    }

    vector<int> C(N);
    for (int i = 0; i < N; i++) {
        C[i] = i;
    }
    sort(C.begin(), C.end(), [&] (int a, int b) {return S[a] * Q[b] < Q[a] * S[b];});

    int ans = 0, apos = 0;
    pair<long long, long long> acst;
    for (int i = 0; i < N; i++) {
        mod(Q[C[i]], 1, 20000, 1);

        int cur = 0;
        long long sum = 0;
        qry(W * Q[C[i]] / S[C[i]], 1, 20000, 1, cur, sum);
        
        pair<long long, long long> cst = make_pair(sum * S[C[i]], Q[C[i]]);
        if (cur > ans || (cur == ans && cst.first * acst.second < cst.second * acst.first)) {
            ans = cur;
            apos = i;
            acst = cst;
        }
    }
    cout << ans << '\n';
    vector<int> pos;
    for (int i = 0; i <= apos; i++) {
        pos.push_back(C[i]);
    }
    sort(pos.begin(), pos.end(), [&] (int a, int b) {return Q[a] < Q[b];});
    for (int i = 0; i < ans; i++) {
        cout << pos[i] + 1 << '\n';
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...