Submission #1036283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036283		thinknoexit	Hiring (IOI09_hiring)	C++17	34 / 100	137 ms	25472 KiB

hiring

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct A {
    ll s, q;
    int idx;
    bool operator < (const A& o) const {
        return s * o.q < q * o.s;
    }
} a[500500], ans;
int cnt[500500], L[500500], fw_c[20020];
ll fw[20020], sum[500500];
void update(int v, int w) {
    for (;v <= 20000;v += v & -v) fw[v] += w, fw_c[v]++;
}
ll query(int v) {
    ll ans = 0;
    for (;v > 0;v -= v & -v) ans += fw[v];
    return ans;
}
ll query_c(int v) {
    ll ans = 0;
    for (;v > 0;v -= v & -v) ans += fw_c[v];
    return ans;
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    ll w;
    cin >> n >> w;
    for (int i = 1;i <= n;i++) {
        cin >> a[i].s >> a[i].q;
        a[i].idx = i;
    }
    sort(a + 1, a + 1 + n);
    int mx = -1;
    bool fi = 0;
    // S_a * (sum Q) <= W * Q_a
    for (int i = 1;i <= n;i++) {
        if (a[i].s > w) continue;
        int l = 0, r = 20000;
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if (a[i].s * (query(mid) + a[i].q) <= w * a[i].q) l = mid;
            else r = mid - 1;
        }
        L[i] = l;
        cnt[i] = query_c(l) + 1;
        sum[i] = a[i].q + query(l);
        ll ava = (w * a[i].q / a[i].s - sum[i]) / (l + 1);
        cnt[i] += ava;
        sum[i] += (l + 1) * ava;
        A now = { sum[i] * a[i].s, a[i].q, i };
        if (cnt[i] > mx) {
            mx = cnt[i];
            ans = now;
        }
        else if (cnt[i] == mx) ans = min(ans, now);
        update(a[i].q, a[i].q);
    }
    if (mx == -1) {
        cout << 0;
        return 0;
    }
    vector<int> res;
    res.push_back(ans.idx);
    int idx = ans.idx;
    ll now = a[idx].q;
    for (int i = 1;i < idx;i++) {
        if (a[i].q <= L[idx]) res.push_back(i), now += a[i].q;
    }
    for (int i = 1;i < idx;i++) {
        if (a[i].q == L[idx] + 1 && a[idx].s * (now + a[i].q) <= w * a[idx].q)
            res.push_back(i), now += a[i].q;
    }
    cout << mx << '\n';
    for (auto& x : res) cout << a[x].idx << '\n';
    //for (int i = 1;i <= n;i++) cout << cnt[i] << ' ';
    return 0;
}

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:37:10: warning: unused variable 'fi' [-Wunused-variable]
   37 |     bool fi = 0;
      |          ^~

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