oj.uz

Submission #856384

# Submission time Handle Problem Language Result Execution time Memory
856384 2023-10-03T09:33:39 Z MilosMilutinovic Hiring (IOI09_hiring) C++14
30 / 100
 801 ms 25912 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;
long long s[N], q[N];
pair<long long, int> st[4 * M];
 
struct frac {
    int p;
    int q;
};
 
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[j] < 1.0 * s[j] * q[i]; });
    frac res;
    res.p = 1e18;
    res.q = 1;
    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]] <= (w - s[order[i]]) * q[order[i]]) {
                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.p * q[order[i]] > (sum.first * s[order[i]] + s[order[i]] * q[order[i]]) * res.q) {
                res.p = sum.first * s[order[i]] + s[order[i]] * q[order[i]];
                res.q = q[order[i]];
                index = i;
            }
        } else if(cnt < sum.second) {
            cnt = sum.second;
            res.p = sum.first * s[order[i]] + s[order[i]] * q[order[i]];
            res.q = q[order[i]];
            index = i;
        }
        update(0, 0, M - 1, q[order[i]]);
    }
    vector<int> ans;
    ans.push_back(order[index]);
    vector<pair<int, int>> have;
    for(int i = 0; i < index; i++) have.push_back({q[order[i]], order[i]});
    sort(have.begin(), have.end());
    for(int i = 0; i < cnt; i++) ans.push_back(have[i].second);
    sort(ans.begin(), ans.end());
    cout << cnt+1 << "\n";
    for(int i=1;i<=cnt+1;i++) cout<<i<<"\n";
    return 0;
}

Subtask #1
13.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 4700 KB Partially correct
2 Partially correct 1 ms 4952 KB Partially correct
3 Partially correct 1 ms 4700 KB Partially correct
4 Partially correct 1 ms 4700 KB Partially correct
5 Partially correct 1 ms 4700 KB Partially correct
6 Partially correct 3 ms 4696 KB Partially correct
7 Partially correct 3 ms 4700 KB Partially correct
8 Partially correct 5 ms 4700 KB Partially correct
9 Partially correct 7 ms 4700 KB Partially correct
10 Incorrect 13 ms 4776 KB Output isn't correct
11 Partially correct 11 ms 4952 KB Partially correct
12 Partially correct 16 ms 4952 KB Partially correct
13 Partially correct 14 ms 4700 KB Partially correct
14 Incorrect 30 ms 5212 KB Output isn't correct
15 Partially correct 34 ms 5104 KB Partially correct

Subtask #2
8.0 / 28.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 4696 KB Partially correct
2 Partially correct 1 ms 4696 KB Partially correct
3 Partially correct 2 ms 4700 KB Partially correct
4 Partially correct 39 ms 4944 KB Partially correct
5 Incorrect 106 ms 5592 KB Output isn't correct
6 Incorrect 526 ms 17096 KB Output isn't correct
7 Incorrect 630 ms 22228 KB Output isn't correct

Subtask #3
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 4696 KB Partially correct
2 Partially correct 2 ms 4700 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 4952 KB Partially correct
2 Partially correct 2 ms 4700 KB Partially correct
3 Partially correct 2 ms 4696 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 2 ms 4744 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 174 ms 8020 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 320 ms 14948 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 745 ms 24032 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 801 ms 25912 KB Output isn't correct
2 Halted 0 ms 0 KB -