oj.uz

Submission #715357

# Submission time Handle Problem Language Result Execution time Memory
715357 2023-03-26T14:37:06 Z Ahmed57 Hiring (IOI09_hiring) C++14
73 / 100
 1123 ms 63496 KB 
#include <bits/stdc++.h>

using namespace std;

signed main(){
    long long n;
    long double w;
    cin>>n>>w;
    vector<pair<long double,pair<long double,long long>>> v;
    for(int i = 0;i<n;i++){
        long double s,q;cin>>s>>q;
        v.push_back({s/q,{q,i+1}});
    }
    sort(v.begin(),v.end());
    priority_queue<pair<long double,int>> q,p;
    long double sum = 0;
    long long ma = 0,ind;
    for(int i = 0;i<v.size();i++){
        p.push({-v[i].second.first,v[i].second.second});
        sum+=(-p.top().first);
        q.push({-p.top().first,p.top().second});
        p.pop();
        long double no =sum*v[i].first;
        while(no>w){
            pair<long double,int>pa = q.top();
            q.pop();
            sum-=pa.first;
            p.push({-pa.first,pa.second});
            no =sum*v[i].first;
        }
        if(q.size()>=ma){
            ma=q.size();
            ind = i;
        }
    }
    while(!q.empty())q.pop();
    while(!p.empty())p.pop();
    sum=0;
    for(int i = 0;i<=ind;i++){
        p.push({-v[i].second.first,v[i].second.second});
        sum+=(-p.top().first);
        q.push({-p.top().first,p.top().second});
        p.pop();
        long double no =sum*v[i].first;
        while(no>w){
            pair<long double,int>pa = q.top();
            q.pop();
            sum-=pa.first;
            p.push({-pa.first,pa.second});
            no =sum*v[i].first;
        }
    }
    cout<<q.size()<<endl;
    while(q.size()){
        cout<<q.top().second<<"\n";
        q.pop();
    }
}

Compilation message

hiring.cpp: In function 'int main()':
hiring.cpp:18:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, std::pair<long double, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int i = 0;i<v.size();i++){
      |                   ~^~~~~~~~~
hiring.cpp:31:20: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<long double, int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   31 |         if(q.size()>=ma){
      |            ~~~~~~~~^~~~
hiring.cpp:17:22: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   17 |     long long ma = 0,ind;
      |                      ^~~

Subtask #1
22.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Partially correct 0 ms 212 KB Partially correct
3 Partially correct 0 ms 212 KB Partially correct
4 Correct 0 ms 212 KB Output is correct
5 Partially correct 1 ms 212 KB Partially correct
6 Correct 3 ms 468 KB Output is correct
7 Partially correct 4 ms 468 KB Partially correct
8 Partially correct 5 ms 664 KB Partially correct
9 Correct 8 ms 848 KB Output is correct
10 Correct 9 ms 928 KB Output is correct
11 Partially correct 11 ms 988 KB Partially correct
12 Correct 14 ms 1260 KB Output is correct
13 Partially correct 16 ms 1528 KB Partially correct
14 Correct 24 ms 1956 KB Output is correct
15 Partially correct 29 ms 2256 KB Partially correct

Subtask #2
24.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Partially correct 0 ms 212 KB Partially correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 35 ms 3160 KB Output is correct
5 Correct 112 ms 7848 KB Output is correct
6 Partially correct 632 ms 44076 KB Partially correct
7 Correct 873 ms 53872 KB Output is correct

Subtask #3
3.0 / 6.0

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

Subtask #4
3.0 / 6.0

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

Subtask #5
3.0 / 6.0

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

Subtask #6
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 235 ms 15768 KB Partially correct
2 Partially correct 241 ms 15672 KB Partially correct
3 Correct 250 ms 15664 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 28800 KB Output is correct
2 Correct 433 ms 28848 KB Output is correct
3 Correct 435 ms 28860 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 999 ms 62128 KB Output is correct
2 Correct 967 ms 62160 KB Output is correct
3 Correct 980 ms 62292 KB Output is correct

Subtask #9
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1113 ms 63496 KB Output is correct
2 Partially correct 1104 ms 63348 KB Partially correct
3 Correct 1123 ms 63380 KB Output is correct