oj.uz

Submission #1036303

# Submission time Handle Problem Language Result Execution time Memory
1036303 2024-07-27T08:30:29 Z thinknoexit Hiring (IOI09_hiring) C++17
34 / 100
 135 ms 20136 KB 
#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;
}
int query_c(int v) {
    int 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;
    // 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 (query(mid) + a[i].q <= w * a[i].q / a[i].s) 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] += ava * (l + 1);
        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;
    int idx = ans.idx;
    res.push_back(idx);
    ll now = a[idx].q;
    for (int i = 1;i < idx;i++) {
        if (a[i].s > w) continue;
        if (a[i].q <= L[idx]) res.push_back(i), now += a[i].q;
    }
    for (int i = 1;i < idx;i++) {
        if (a[i].s > w) continue;
        if (a[i].q == L[idx] + 1 && now + a[i].q <= w * a[idx].q / a[idx].s)
            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;
}

Subtask #1
18.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Incorrect 1 ms 604 KB Output isn't correct
9 Incorrect 2 ms 860 KB Output isn't correct
10 Incorrect 2 ms 860 KB Output isn't correct
11 Correct 2 ms 824 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Incorrect 3 ms 860 KB Output isn't correct
14 Incorrect 4 ms 1116 KB Output isn't correct
15 Incorrect 4 ms 1116 KB Output isn't correct

Subtask #2
16.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Incorrect 6 ms 1492 KB Output isn't correct
5 Correct 15 ms 3160 KB Output is correct
6 Incorrect 82 ms 12344 KB Output isn't correct
7 Incorrect 105 ms 16208 KB Output isn't correct

Subtask #3
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 4920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 8528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 121 ms 18264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 135 ms 20136 KB Output isn't correct
2 Halted 0 ms 0 KB -