oj.uz

Submission #856190

# Submission time Handle Problem Language Result Execution time Memory
856190 2023-10-02T19:05:13 Z DAleksa Hiring (IOI09_hiring) C++17
53 / 100
 780 ms 25272 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);
    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[i] < 1.0 * s[j] / q[j]; });
    double res = 1e18;
    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]] / 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 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4632 KB Output is correct
6 Correct 3 ms 4700 KB Output is correct
7 Partially correct 3 ms 4700 KB Partially correct
8 Correct 5 ms 4700 KB Output is correct
9 Correct 8 ms 4772 KB Output is correct
10 Incorrect 8 ms 4700 KB Output isn't correct
11 Correct 11 ms 4956 KB Output is correct
12 Partially correct 11 ms 4956 KB Partially correct
13 Correct 15 ms 4700 KB Output is correct
14 Incorrect 20 ms 5212 KB Output isn't correct
15 Partially correct 23 ms 4948 KB Partially correct

Subtask #2
12.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Partially correct 1 ms 4700 KB Partially correct
3 Correct 1 ms 4696 KB Output is correct
4 Partially correct 29 ms 5152 KB Partially correct
5 Incorrect 98 ms 5620 KB Output isn't correct
6 Incorrect 471 ms 16892 KB Output isn't correct
7 Incorrect 646 ms 22048 KB Output isn't correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 2 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 3 ms 4696 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 3 ms 4700 KB Output is correct

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 176 ms 8024 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 337 ms 15368 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 690 ms 23096 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 780 ms 25272 KB Output isn't correct
2 Halted 0 ms 0 KB -