oj.uz

Submission #856179

# Submission time Handle Problem Language Result Execution time Memory
856179 2023-10-02T18:50:49 Z DAleksa Hiring (IOI09_hiring) C++17
30 / 100
 759 ms 26072 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 = 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 + 2 << "\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 4444 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 4440 KB Partially correct
6 Partially correct 3 ms 4700 KB Partially correct
7 Partially correct 3 ms 4444 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 11 ms 4788 KB Partially correct
12 Partially correct 11 ms 4696 KB Partially correct
13 Partially correct 16 ms 4696 KB Partially correct
14 Incorrect 23 ms 5212 KB Output isn't correct
15 Partially correct 25 ms 5092 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 4560 KB Partially correct
4 Partially correct 29 ms 4956 KB Partially correct
5 Incorrect 94 ms 5508 KB Output isn't correct
6 Incorrect 470 ms 16828 KB Output isn't correct
7 Incorrect 644 ms 22044 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 2 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 4700 KB Partially correct
2 Partially correct 2 ms 4700 KB Partially correct
3 Partially correct 2 ms 4856 KB Partially correct

Subtask #5
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 4696 KB Partially correct
2 Partially correct 3 ms 4932 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 184 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 325 ms 14920 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 716 ms 24264 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 759 ms 26072 KB Output isn't correct
2 Halted 0 ms 0 KB -