oj.uz

Submission #207605

# Submission time Handle Problem Language Result Execution time Memory
207605 2020-03-08T05:52:34 Z dolphingarlic Hiring (IOI09_hiring) C++14
100 / 100
 465 ms 12944 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

struct Worker {
    int s, id;
    double ratio;
};
bool operator<(Worker A, Worker B) {
    if (A.s == B.s) return A.ratio < B.ratio;
    return A.s < B.s;
}
bool cmp(Worker A, Worker B) {
    if (A.ratio == B.ratio) return A.s < B.s;
    return A.ratio < B.ratio;
}

Worker workers[500001];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    ll m;
    cin >> n >> m;
    FOR(i, 0, n) {
        int s, q;
        cin >> q >> s;
        workers[i] = {s, i + 1, (double)q / s};
    }
    sort(workers, workers + n, cmp);

    int best_pos = -1, mx_workers = 0;
    double best_pay = 1e18;

    priority_queue<Worker> pq;
    ll sm = 0;
    FOR(i, 0, n) {
        pq.push(workers[i]);
        sm += workers[i].s;
        while (sm * workers[i].ratio > m) {
            sm -= pq.top().s;
            pq.pop();
        }

        if (pq.size() > mx_workers) {
            mx_workers = pq.size();
            best_pay = sm * workers[i].ratio;
            best_pos = i;
        } else if (pq.size() == mx_workers && sm * workers[i].ratio < best_pay) {
            best_pay = sm * workers[i].ratio;
            best_pos = i;
        }
    }

    while (pq.size()) pq.pop();
    sm = 0;
    FOR(i, 0, n) {
        pq.push(workers[i]);
        sm += workers[i].s;
        while (sm * workers[i].ratio > m) {
            sm -= pq.top().s;
            pq.pop();
        }

        if (i == best_pos) {
            cout << mx_workers << '\n';
            while (pq.size()) {
                cout << pq.top().id << '\n';
                pq.pop();
            }
            return 0;
        }
    }
    return 0;
}

Compilation message

hiring.cpp: In function 'int main()':
hiring.cpp:47:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (pq.size() > mx_workers) {
             ~~~~~~~~~~^~~~~~~~~~~~
hiring.cpp:51:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         } else if (pq.size() == mx_workers && sm * workers[i].ratio < best_pay) {
                    ~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 380 KB Output is correct
7 Correct 6 ms 376 KB Output is correct
8 Correct 6 ms 376 KB Output is correct
9 Correct 7 ms 504 KB Output is correct
10 Correct 7 ms 508 KB Output is correct
11 Correct 7 ms 504 KB Output is correct
12 Correct 9 ms 672 KB Output is correct
13 Correct 9 ms 504 KB Output is correct
14 Correct 12 ms 760 KB Output is correct
15 Correct 13 ms 760 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 380 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 15 ms 888 KB Output is correct
5 Correct 37 ms 1784 KB Output is correct
6 Correct 225 ms 7404 KB Output is correct
7 Correct 320 ms 10984 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 296 KB Output is correct
3 Correct 5 ms 376 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 3316 KB Output is correct
2 Correct 83 ms 3312 KB Output is correct
3 Correct 92 ms 3316 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 5764 KB Output is correct
2 Correct 139 ms 5612 KB Output is correct
3 Correct 145 ms 5744 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 11660 KB Output is correct
2 Correct 380 ms 11624 KB Output is correct
3 Correct 360 ms 11624 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 12900 KB Output is correct
2 Correct 409 ms 12944 KB Output is correct
3 Correct 465 ms 12768 KB Output is correct