oj.uz

Submission #856196

# Submission time Handle Problem Language Result Execution time Memory
856196 2023-10-02T19:15:33 Z DAleksa Hiring (IOI09_hiring) C++17
53 / 100
 935 ms 33532 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 double 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[j] < 1.0 * s[j] * q[i]; });
    long 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]] <= (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 > 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";
    assert(jebala_vas_konstrukcija.size() == cnt + 1);
    for(int i : jebala_vas_konstrukcija) cout << i + 1 << "\n";
    return 0;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from hiring.cpp:1:
hiring.cpp: In function 'int main()':
hiring.cpp:79:43: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   79 |     assert(jebala_vas_konstrukcija.size() == cnt + 1);
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

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 4952 KB Output is correct
6 Correct 3 ms 4700 KB Output is correct
7 Partially correct 4 ms 4716 KB Partially correct
8 Correct 6 ms 4696 KB Output is correct
9 Correct 8 ms 4696 KB Output is correct
10 Incorrect 9 ms 4696 KB Output isn't correct
11 Correct 12 ms 4952 KB Output is correct
12 Partially correct 13 ms 4800 KB Partially correct
13 Correct 18 ms 4804 KB Output is correct
14 Incorrect 23 ms 5096 KB Output isn't correct
15 Partially correct 29 ms 5084 KB Partially correct

Subtask #2
12.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4696 KB Output is correct
2 Partially correct 1 ms 4700 KB Partially correct
3 Correct 1 ms 4700 KB Output is correct
4 Partially correct 37 ms 4944 KB Partially correct
5 Incorrect 109 ms 7672 KB Output isn't correct
6 Incorrect 563 ms 21644 KB Output isn't correct
7 Incorrect 749 ms 30500 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 2 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 3 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 2 ms 4700 KB Output is correct
2 Correct 3 ms 4700 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 217 ms 12124 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 368 ms 17928 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 856 ms 31972 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 935 ms 33532 KB Output isn't correct
2 Halted 0 ms 0 KB -