Submission #881229

#	Time	Username	Problem	Language	Result	Execution time	Memory
881229		Matjaz	Hiring (IOI09_hiring)	C++14	60 / 100	596 ms	22896 KiB

hiring

//
//  IOI2009Salesman.cpp
//
//
//  Created by Matjaz Leonardis on 11/11/2023.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

struct worker{
    long long S;
    long long Q;
    int index;
    bool operator<(const worker& other) const {
        return S * other.Q < other.S * Q;
    }
};

struct w2{
    long long Q;
    int index;
    bool operator<(const w2& other) const {
        return Q < other.Q;
    }
};

int N;
long long W;

int main(){
    
    cin >> N >> W;
    vector<worker> w(N);
    
    for (int i=0;i<N;i++){
        cin >> w[i].S >> w[i].Q;
        w[i].index = i + 1;
    }
    
    sort(w.begin(), w.end());
    
    long long total = 0;
    priority_queue<w2> Q;
    int best = 0;
    for (int i=0;i<N;i++){
        w2 x;
        x.Q = w[i].Q;
        x.index = w[i].index;
        Q.push(x);
        total += x.Q;
        while (total * w[i].S > W * w[i].Q){
            total -= Q.top().Q;
            Q.pop();
        }
        
        if (Q.size() > best) best = Q.size();
    }
    
    cout << best << endl;
    
    total = 0;
    while (!Q.empty()) Q.pop();
    for (int i=0;i<N;i++){
        w2 x;
        x.Q = w[i].Q;
        x.index = w[i].index;
        Q.push(x);
        total += x.Q;
        while (total * w[i].S > W * w[i].Q){
            total -= Q.top().Q;
            Q.pop();
        }
        
        if (Q.size() == best){
            while (!Q.empty()){
                cout << Q.top().index << endl;
                Q.pop();
            }
            break;
        }
    }
    
    
    return 0;
}

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:61:22: warning: comparison of integer expressions of different signedness: 'std::priority_queue<w2>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |         if (Q.size() > best) best = Q.size();
      |             ~~~~~~~~~^~~~~~
hiring.cpp:79:22: warning: comparison of integer expressions of different signedness: 'std::priority_queue<w2>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   79 |         if (Q.size() == best){
      |             ~~~~~~~~~^~~~~~~

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