oj.uz

답안 #856382

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
856382 2023-10-03T09:31:31 Z MilosMilutinovic Hiring (IOI09_hiring) C++14
30 / 100
 799 ms 25496 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

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 4700 KB Partially correct
2 Partially correct 1 ms 4700 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 4700 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 10 ms 4696 KB Output isn't correct
11 Partially correct 10 ms 4776 KB Partially correct
12 Partially correct 18 ms 4776 KB Partially correct
13 Partially correct 19 ms 4804 KB Partially correct
14 Incorrect 20 ms 5212 KB Output isn't correct
15 Partially correct 23 ms 5108 KB Partially correct

Subtask #2
8.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 4700 KB Partially correct
2 Partially correct 1 ms 4700 KB Partially correct
3 Partially correct 1 ms 4700 KB Partially correct
4 Partially correct 29 ms 5148 KB Partially correct
5 Incorrect 90 ms 5592 KB Output isn't correct
6 Incorrect 494 ms 16772 KB Output isn't correct
7 Incorrect 659 ms 22288 KB Output isn't correct

Subtask #3
3.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 2 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

# 결과 실행 시간 메모리 Grader output
1 Partially correct 2 ms 4700 KB Partially correct
2 Partially correct 3 ms 4956 KB Partially correct
3 Partially correct 2 ms 4956 KB Partially correct

Subtask #5
3.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 2 ms 4696 KB Partially correct
2 Partially correct 2 ms 4696 KB Partially correct
3 Partially correct 2 ms 4748 KB Partially correct

Subtask #6
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 176 ms 8028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 362 ms 15632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 792 ms 23236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 799 ms 25496 KB Output isn't correct
2 Halted 0 ms 0 KB -