제출 #1337723

#제출 시각아이디문제언어결과실행 시간메모리
1337723k1r1t0Hiring (IOI09_hiring)C++20
100 / 100
213 ms31652 KiB
#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 510000;

int n, s[N], q[N], w;
vector<array<int, 3>> vec;
bool bad[N], take[N];

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> w;
    for (int i = 1; i <= n; i++)
        cin >> s[i] >> q[i];
    for (int i = 1; i <= n; i++)    
        vec.push_back({s[i], q[i], i});
    sort(begin(vec), end(vec), [&](auto a, auto b) {
        return a[0] * b[1] < b[0] * a[1];
    });
    vector<int> qq(n);
    iota(begin(qq), end(qq), 0ll);
    sort(begin(qq), end(qq), [&](int i, int j) {
        return vec[i][1] > vec[j][1];
    });
    // sumQ * maxS/Q <= W
    int optcnt = 0, optsum = 0, optq = 0, opts = 0, tm = n, sum = 0, cnt = 0;
    for (int i = n - 1; i >= 0; i--) {
        int s = vec[i][0];
        int q = vec[i][1];
        while (!qq.empty() && (sum + vec[qq.back()][1]) * s <= w * q) {
            if (!bad[qq.back()]) {
                cnt++;
                sum += vec[qq.back()][1];
                take[qq.back()] = true;
            }
            qq.pop_back();
        }
        if (cnt > optcnt || (cnt == optcnt && sum * s * optq <= optsum * q * opts)) {
            optcnt = cnt;
            optsum = sum;
            optq = q;
            opts = s;
            tm = i;
        }
        bad[i] = true;
        if (take[i]) {
            take[i] = false;
            cnt--;
            sum -= vec[i][1];
        }
    }
    if (optcnt == 0) {
        cout << 0;
        return 0;
    }
    cout << optcnt << '\n';
    qq = vector<int>(n);
    iota(begin(qq), end(qq), 0ll);
    sort(begin(qq), end(qq), [&](int i, int j) {
        return vec[i][1] > vec[j][1];
    });
    for (int i = 0; i < n; i++)
        bad[i] = take[i] = false;
    assert(tm != n);
    sum = 0; cnt = 0;
    for (int i = n - 1; i >= 0; i--) {
        while (!qq.empty() && (sum + vec[qq.back()][1]) * vec[i][0] <= w * vec[i][1]) {
            if (!bad[qq.back()]) {
                cnt++;
                sum += vec[qq.back()][1];
                take[qq.back()] = true;
            }
            qq.pop_back();
        }
        if (i == tm) {
            vector<int> fin;
            for (int i = 0; i < n; i++)
                if (take[i])
                    fin.push_back(vec[i][2]);
            bool f = true;
            for (int x : fin) {
                if (!f) cout << '\n';
                f = false;
                cout << x;
            }
            return 0;
        }
        bad[i] = true;
        if (take[i]) {
            take[i] = false;
            cnt--;
            sum -= vec[i][1];
        }
    }
}
#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...