Submission #881231

#	Time	Username	Problem	Language	Result	Execution time	Memory
881231		Matjaz	Hiring (IOI09_hiring)	C++14	100 / 100	569 ms	17900 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;
    long long minMoneyQnS = 0;
    long long minMoneyQd = 0;
    int besti = 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){
            if (total * w[i].S * minMoneyQd < w[i].Q * minMoneyQnS){
                minMoneyQd = w[i].Q;
                minMoneyQnS = total * w[i].S;
                besti = i;
            }
            
            
        }
        
        if (Q.size() > best){
            best = Q.size();
            minMoneyQd = w[i].Q;
            minMoneyQnS = total * w[i].S;
            besti = i;
        }
    }
    
    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 (i == besti){
            while (!Q.empty()){
                cout << Q.top().index << endl;
                Q.pop();
            }
            break;
        }
    }
    
    
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 30 / 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