oj.uz

Submission #856177

# Submission time Handle Problem Language Result Execution time Memory
856177 2023-10-02T18:47:30 Z DAleksa Hiring (IOI09_hiring) C++17
53 / 100
 812 ms 24788 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 * 1.0 * s[order[i]] / q[order[i]] + s[order[i]]) {
                res = sum.first * 1.0 * s[order[i]] / q[order[i]] + s[order[i]];
                index = i;
            }
        } else if(cnt < sum.second) {
            cnt = sum.second;
            res = sum.first * 1.0 * s[order[i]] / q[order[i]] + s[order[i]];
            index = i;
        }
        update(0, 0, M - 1, q[order[i]]);
    }
    vector<int> jebala_vas_konstrukcija;
    jebala_vas_konstrukcija.push_back(order[index]);
    vector<pair<int, int>> smarate;
    for(int i = 0; i < index; i++) smarate.push_back({q[order[i]], order[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
23.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 3 ms 4700 KB Output is correct
7 Partially correct 3 ms 4696 KB Partially correct
8 Correct 6 ms 4856 KB Output is correct
9 Correct 7 ms 4700 KB Output is correct
10 Incorrect 9 ms 4880 KB Output isn't correct
11 Correct 12 ms 4956 KB Output is correct
12 Partially correct 11 ms 4684 KB Partially correct
13 Correct 15 ms 4700 KB Output is correct
14 Incorrect 21 ms 5200 KB Output isn't correct
15 Partially correct 24 ms 4948 KB Partially correct

Subtask #2
12.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Partially correct 1 ms 4444 KB Partially correct
3 Correct 1 ms 4568 KB Output is correct
4 Partially correct 30 ms 4956 KB Partially correct
5 Incorrect 112 ms 5508 KB Output isn't correct
6 Incorrect 495 ms 16652 KB Output isn't correct
7 Incorrect 675 ms 21444 KB Output isn't correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4700 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4700 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 189 ms 8028 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 335 ms 15108 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 729 ms 23752 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 812 ms 24788 KB Output isn't correct
2 Halted 0 ms 0 KB -