oj.uz

Submission #856168

# Submission time Handle Problem Language Result Execution time Memory
856168 2023-10-02T18:35:53 Z DAleksa Hiring (IOI09_hiring) C++17
30 / 100
 774 ms 25564 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;
int s[N], q[N];
pair<long long, int> st[4 * M];

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);
    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[i] < 1.0 * s[j] / q[j]; });
    double res = 1e18;
    int cnt = 0, index = order[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]] / q[order[i]] + s[order[i]] <= w) {
                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 > sum.first) {
                res = sum.first;
                index = i;
            }
        } else if(cnt < sum.second) {
            cnt = sum.second;
            res = sum.first;
            index = i;
        }
        update(0, 0, M - 1, q[order[i]]);
    }
    vector<int> jebala_vas_konstrukcija;
    jebala_vas_konstrukcija.push_back(index);
    vector<pair<int, int>> smarate;
    for(int i = 0; i < index; i++) smarate.push_back({q[order[i]], i});
    sort(smarate.begin(), smarate.end());
    for(int i = 0; i < cnt; i++) jebala_vas_konstrukcija.push_back(smarate[i].second);
    sort(jebala_vas_konstrukcija.begin(), jebala_vas_konstrukcija.end());
    cout << jebala_vas_konstrukcija.size() << "\n";
    for(int i : jebala_vas_konstrukcija) cout << i + 1 << "\n";
    return 0;
}

Subtask #1
13.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 4440 KB Partially correct
2 Partially correct 1 ms 4440 KB Partially correct
3 Partially correct 1 ms 4444 KB Partially correct
4 Partially correct 1 ms 4444 KB Partially correct
5 Partially correct 1 ms 4444 KB Partially correct
6 Partially correct 3 ms 4700 KB Partially correct
7 Partially correct 5 ms 4440 KB Partially correct
8 Partially correct 5 ms 4700 KB Partially correct
9 Partially correct 7 ms 4700 KB Partially correct
10 Incorrect 12 ms 4760 KB Output isn't correct
11 Partially correct 11 ms 4784 KB Partially correct
12 Partially correct 11 ms 4700 KB Partially correct
13 Partially correct 14 ms 4820 KB Partially correct
14 Incorrect 19 ms 5208 KB Output isn't correct
15 Partially correct 28 ms 5108 KB Partially correct

Subtask #2
8.0 / 28.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 4444 KB Partially correct
2 Partially correct 1 ms 4444 KB Partially correct
3 Partially correct 1 ms 4700 KB Partially correct
4 Partially correct 29 ms 4948 KB Partially correct
5 Incorrect 101 ms 5472 KB Output isn't correct
6 Incorrect 471 ms 17164 KB Output isn't correct
7 Incorrect 714 ms 21536 KB Output isn't correct

Subtask #3
3.0 / 6.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

Subtask #4
3.0 / 6.0

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

Subtask #5
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 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 174 ms 8032 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 332 ms 16388 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 734 ms 22240 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 774 ms 25564 KB Output isn't correct
2 Halted 0 ms 0 KB -