Submission #491565

#	Time	Username	Problem	Language	Result	Execution time	Memory
491565		Alexandruabcde	Hiring (IOI09_hiring)	C++14	99 / 100	299 ms	20336 KiB

hiring

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair <int, int> PII;
constexpr int NMAX = 5e5 + 5;

int N;
LL W;

struct Candidate {
    int Q, S;
    double XMin;
    int ind;

    bool operator < (const Candidate &other) {
        return XMin < other.XMin;
    }
};
Candidate A[NMAX];

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> W;

    for (int i = 1; i <= N; ++ i ) {
        cin >> A[i].S >> A[i].Q;
        A[i].XMin = 1.0 * A[i].S / A[i].Q;
        A[i].ind = i;
    }
    sort(A+1, A+N+1);
}

void Solve () {
    priority_queue<PII, vector<PII>, less<PII> > H;
    LL sum = 0;
    int ans = 0, bestInd = 0;
    LL cost = 1000000000000000000;

    for (int i = 1; i <= N; ++ i ) {
        H.push({A[i].Q, i});
        sum += 1LL * A[i].Q;

        while (1LL * A[i].XMin * sum > W) {
            PII elim = H.top();
            H.pop();
            sum -= elim.first;
        }

        if (H.size() > ans) {
            ans = H.size();
            bestInd = i;
            cost = 1LL * A[i].XMin * sum;
        }
        else if (H.size() == ans && cost > 1LL * A[i].XMin * sum) {
            cost = 1LL * A[i].XMin * sum;
            bestInd = i;
        }
    }

    cout << ans << '\n';
    while (!H.empty()) H.pop();

    sum = 0;
    for (int i = 1; i <= bestInd; ++ i ) {
        H.push({A[i].Q, i});
        sum += 1LL * A[i].Q;

        while (1LL * A[i].XMin * sum > W) {
            PII elim = H.top();
            H.pop();
            sum -= elim.first;
        }
    }

    while (!H.empty()) {
        cout << A[H.top().second].ind << '\n';
        H.pop();
    }
}

int main () {
    Read();

    Solve();

    return 0;
}

Compilation message (stderr)

hiring.cpp: In function 'void Solve()':
hiring.cpp:53:22: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::less<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |         if (H.size() > ans) {
      |             ~~~~~~~~~^~~~~
hiring.cpp:58:27: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::less<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |         else if (H.size() == ans && cost > 1LL * A[i].XMin * sum) {
      |                  ~~~~~~~~~^~~~~~

• Subtask 1: 29 / 30
• Subtask 2: 28 / 28
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 6 / 6
• Subtask 7: 6 / 6
• Subtask 8: 6 / 6
• Subtask 9: 6 / 6