Submission #856212

#	Time	Username	Problem	Language	Result	Execution time	Memory
856212		DAleksa	Hiring (IOI09_hiring)	C++17	53 / 100	748 ms	24788 KiB

hiring

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 5e5 + 10, M = 2e4 + 10;
int n;
long long w;
long long s[N], q[N];
pair<long long, int> st[4 * M];

struct frac {
    int p;
    int q;
};

void update(int index, int l, int r, int x) {
    if(l > r || r < x || x < l) return;
    if(l == r) {
        st[index].first += x;
        st[index].second += 1;
        return;
    }
    int mid = (l + r) / 2;
    update(2 * index + 1, l, mid, x);
    update(2 * index + 2, mid + 1, r, x);
    st[index].first = st[2 * index + 1].first + st[2 * index + 2].first;
    st[index].second = st[2 * index + 1].second + st[2 * index + 2].second;
}

pair<long long, int> get(int index, int l, int r, int L, int R) {
    if(l > r || r < L || R < l) return {0, 0};
    if(L <= l && r <= R) return st[index];
    int mid = (l + r) / 2;
    pair<long long, int> p1 = get(2 * index + 1, l, mid, L, R);
    pair<long long, int> p2 = get(2 * index + 2, mid + 1, r, L, R);
    return {p1.first + p2.first, p1.second + p2.second};
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    for(int i = 0; i < 4 * M; i++) st[i].first = st[i].second = 0;
    cin >> n >> w;
    for(int i = 0; i < n; i++) cin >> s[i] >> q[i];
    int order[n];
    iota(order, order + n, 0);
    sort(order, order + n, [&](int i, int j) { return 1.0 * s[i] * q[j] < 1.0 * s[j] * q[i]; });
    frac res;
    res.p = 1e18;
    res.q = 1;
    int cnt = 0, index = 0;
    for(int i = 0; i < n; i++) {
        int l = 0, r = M - 1;
        int ans = l;
        while(l <= r) {
            int mid = (l + r) / 2;
            pair<long long, int> sum = get(0, 0, M - 1, 0, mid);
            if(sum.first * 1.0 * s[order[i]] < (w - s[order[i]]) * q[order[i]]) {
                ans = mid;
                l = mid + 1;
            } else r = mid - 1;
        }
        pair<long long, int> sum = get(0, 0, M - 1, 0, ans);
        if(cnt == sum.second) {
            if(res.p * q[order[i]] > (sum.first * s[order[i]] + s[order[i]] * q[order[i]]) * res.q) {
                res.p = sum.first * s[order[i]] + s[order[i]] * q[order[i]];
                res.q = q[order[i]];
                index = i;
            }
        } else if(cnt < sum.second) {
            cnt = sum.second;
            res.p = sum.first * s[order[i]] + s[order[i]] * q[order[i]];
            res.q = q[order[i]];
            index = i;
        }
        update(0, 0, M - 1, q[order[i]]);
    }
    vector<int> ans;
    ans.push_back(order[index]);
    vector<pair<int, int>> have;
    for(int i = 0; i < index; i++) have.push_back({q[order[i]], order[i]});
    sort(have.begin(), have.end());
    for(int i = 0; i < cnt; i++) ans.push_back(have[i].second);
    sort(ans.begin(), ans.end());
    cout << ans.size() << "\n";
    for(int i : ans) cout << i + 1 << "\n";
    return 0;
}

• 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