oj.uz

Submission #856166

# Submission time Handle Problem Language Result Execution time Memory
856166 2023-10-02T18:32:41 Z DAleksa Hiring (IOI09_hiring) C++17
30 / 100
 777 ms 19676 KB 
#include <bits/stdc++.h>

using namespace std;

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};
}

int 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);
    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 4444 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 4560 KB Partially correct
6 Partially correct 3 ms 4696 KB Partially correct
7 Partially correct 3 ms 4444 KB Partially correct
8 Partially correct 5 ms 4728 KB Partially correct
9 Partially correct 7 ms 4700 KB Partially correct
10 Incorrect 9 ms 4788 KB Output isn't correct
11 Partially correct 12 ms 4888 KB Partially correct
12 Partially correct 11 ms 4700 KB Partially correct
13 Partially correct 15 ms 4700 KB Partially correct
14 Incorrect 20 ms 4956 KB Output isn't correct
15 Partially correct 23 ms 4956 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 32 ms 5016 KB Partially correct
5 Incorrect 97 ms 5700 KB Output isn't correct
6 Incorrect 485 ms 12380 KB Output isn't correct
7 Incorrect 645 ms 17020 KB Output isn't correct

Subtask #3
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 4696 KB Partially correct
2 Partially correct 1 ms 4560 KB Partially correct
3 Partially correct 2 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 4888 KB Partially correct
3 Partially correct 2 ms 4700 KB Partially 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 3 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 175 ms 7772 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 354 ms 9940 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 704 ms 17600 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 777 ms 19676 KB Output isn't correct
2 Halted 0 ms 0 KB -