oj.uz

Submission #1036283

# Submission time Handle Problem Language Result Execution time Memory
1036283 2024-07-27T08:10:20 Z thinknoexit Hiring (IOI09_hiring) C++17
34 / 100
 137 ms 25472 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;
}
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

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

Subtask #1
18.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 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 468 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 736 KB Output isn't correct
10 Incorrect 2 ms 860 KB Output isn't correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 3 ms 860 KB Output is correct
13 Incorrect 3 ms 1116 KB Output isn't correct
14 Incorrect 4 ms 1116 KB Output isn't correct
15 Incorrect 5 ms 1560 KB Output isn't correct

Subtask #2
16.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 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 1628 KB Output isn't correct
5 Correct 16 ms 3668 KB Output is correct
6 Incorrect 84 ms 15440 KB Output isn't correct
7 Incorrect 102 ms 20308 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 6236 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 56 ms 10352 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 129 ms 23124 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 137 ms 25472 KB Output isn't correct
2 Halted 0 ms 0 KB -