oj.uz

Submission #856209

# Submission time Handle Problem Language Result Execution time Memory
856209 2023-10-02T19:33:48 Z DAleksa Hiring (IOI09_hiring) C++17
30 / 100
 692 ms 25016 KB 
#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 << "\n";
    return 0;
}

Subtask #1
13.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 4696 KB Partially correct
2 Partially correct 1 ms 4700 KB Partially correct
3 Partially correct 1 ms 4700 KB Partially correct
4 Partially correct 1 ms 4700 KB Partially correct
5 Partially correct 1 ms 4732 KB Partially correct
6 Partially correct 3 ms 4952 KB Partially correct
7 Partially correct 3 ms 4700 KB Partially correct
8 Partially correct 5 ms 4700 KB Partially correct
9 Partially correct 7 ms 4700 KB Partially correct
10 Incorrect 8 ms 4700 KB Output isn't correct
11 Partially correct 10 ms 4952 KB Partially correct
12 Partially correct 12 ms 4800 KB Partially correct
13 Partially correct 14 ms 4700 KB Partially correct
14 Incorrect 18 ms 5092 KB Output isn't correct
15 Partially correct 23 ms 4956 KB Partially correct

Subtask #2
8.0 / 28.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 4700 KB Partially correct
2 Partially correct 1 ms 4700 KB Partially correct
3 Partially correct 1 ms 4700 KB Partially correct
4 Partially correct 27 ms 4956 KB Partially correct
5 Incorrect 92 ms 5620 KB Output isn't correct
6 Incorrect 437 ms 16644 KB Output isn't correct
7 Incorrect 579 ms 22640 KB Output isn't correct

Subtask #3
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 4700 KB Partially correct
2 Partially correct 1 ms 4700 KB Partially correct
3 Partially correct 2 ms 4696 KB Partially correct

Subtask #4
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 4700 KB Partially correct
2 Partially correct 2 ms 4700 KB Partially correct
3 Partially correct 2 ms 4700 KB Partially correct

Subtask #5
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 4700 KB Partially correct
2 Partially correct 2 ms 4700 KB Partially correct
3 Partially correct 2 ms 4700 KB Partially correct

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 165 ms 8044 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 318 ms 15620 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 653 ms 23988 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 692 ms 25016 KB Output isn't correct
2 Halted 0 ms 0 KB -