oj.uz

Submission #856174

# Submission time Handle Problem Language Result Execution time Memory
856174 2023-10-02T18:43:22 Z DAleksa Hiring (IOI09_hiring) C++17
39 / 100
 768 ms 25448 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(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
18.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 4440 KB Partially correct
2 Correct 1 ms 4444 KB Output is correct
3 Partially correct 1 ms 4444 KB Partially 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 4444 KB Partially correct
8 Partially correct 6 ms 4716 KB Partially correct
9 Correct 8 ms 4908 KB Output is correct
10 Incorrect 11 ms 4700 KB Output isn't correct
11 Partially correct 11 ms 4952 KB Partially correct
12 Partially correct 11 ms 4700 KB Partially correct
13 Partially correct 15 ms 4812 KB Partially correct
14 Incorrect 20 ms 5208 KB Output isn't correct
15 Partially correct 24 ms 5116 KB Partially correct

Subtask #2
12.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Partially correct 1 ms 4444 KB Partially correct
3 Correct 1 ms 4700 KB Output is correct
4 Partially correct 30 ms 5132 KB Partially correct
5 Incorrect 95 ms 5588 KB Output isn't correct
6 Incorrect 467 ms 16648 KB Output isn't correct
7 Incorrect 641 ms 21788 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 4696 KB Partially correct
3 Correct 2 ms 4696 KB Output is 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 4696 KB Partially correct
3 Correct 2 ms 4700 KB Output is 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 Correct 2 ms 4700 KB Output is correct

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 177 ms 8108 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 16384 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 688 ms 24016 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 768 ms 25448 KB Output isn't correct
2 Halted 0 ms 0 KB -