oj.uz

Submission #881231

# Submission time Handle Problem Language Result Execution time Memory
881231 2023-11-30T22:58:19 Z Matjaz Hiring (IOI09_hiring) C++14
100 / 100
 569 ms 17900 KB 
//
//  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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 360 KB Output is correct
9 Correct 5 ms 600 KB Output is correct
10 Correct 6 ms 604 KB Output is correct
11 Correct 5 ms 604 KB Output is correct
12 Correct 10 ms 856 KB Output is correct
13 Correct 6 ms 604 KB Output is correct
14 Correct 13 ms 952 KB Output is correct
15 Correct 13 ms 860 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 20 ms 1188 KB Output is correct
5 Correct 43 ms 2256 KB Output is correct
6 Correct 303 ms 9648 KB Output is correct
7 Correct 414 ms 14272 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 4232 KB Output is correct
2 Correct 117 ms 4244 KB Output is correct
3 Correct 115 ms 4232 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 7280 KB Output is correct
2 Correct 197 ms 7108 KB Output is correct
3 Correct 197 ms 7284 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 477 ms 16216 KB Output is correct
2 Correct 486 ms 16580 KB Output is correct
3 Correct 479 ms 16832 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 17856 KB Output is correct
2 Correct 557 ms 17900 KB Output is correct
3 Correct 569 ms 16832 KB Output is correct