oj.uz

Submission #715364

# Submission time Handle Problem Language Result Execution time Memory
715364 2023-03-26T14:44:26 Z Ahmed57 Hiring (IOI09_hiring) C++14
72 / 100
 1314 ms 63464 KB 
#include <bits/stdc++.h>

using namespace std;

signed main(){
    long long n;
    long long 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 = -1;
    long double su = 0.0;
    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;
            su = sum;
        }if(q.size()==ma&&su>no){
            su = no;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:19: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]
   19 |     for(int i = 0;i<v.size();i++){
      |                   ~^~~~~~~~~
hiring.cpp:32: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]
   32 |         if(q.size()>ma){
      |            ~~~~~~~~^~~
hiring.cpp:36:21: 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]
   36 |         }if(q.size()==ma&&su>no){
      |             ~~~~~~~~^~~~

Subtask #1
24.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Partially correct 1 ms 212 KB Partially correct
3 Correct 0 ms 212 KB Output is correct
4 Partially correct 0 ms 212 KB Partially correct
5 Partially correct 1 ms 212 KB Partially correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 4 ms 496 KB Output is correct
8 Correct 5 ms 660 KB Output is correct
9 Correct 9 ms 788 KB Output is correct
10 Partially correct 10 ms 1040 KB Partially correct
11 Correct 12 ms 1036 KB Output is correct
12 Partially correct 13 ms 1240 KB Partially correct
13 Correct 15 ms 1512 KB Output is correct
14 Correct 24 ms 1960 KB Output is correct
15 Partially correct 27 ms 2260 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 1 ms 212 KB Partially correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 36 ms 3116 KB Output is correct
5 Correct 109 ms 7872 KB Output is correct
6 Correct 692 ms 43980 KB Output is correct
7 Partially correct 931 ms 53660 KB Partially 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 1 ms 340 KB Partially correct
3 Correct 1 ms 340 KB Output is correct

Subtask #4
6.0 / 6.0

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

Subtask #5
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is 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 253 ms 15664 KB Partially correct
2 Partially correct 247 ms 15660 KB Partially correct
3 Correct 259 ms 15660 KB Output is correct

Subtask #7
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 452 ms 28812 KB Partially correct
2 Partially correct 468 ms 28900 KB Partially correct
3 Correct 477 ms 28864 KB Output is correct

Subtask #8
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1033 ms 62120 KB Output is correct
2 Partially correct 1004 ms 62160 KB Partially correct
3 Correct 1022 ms 62072 KB Output is correct

Subtask #9
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1159 ms 63388 KB Output is correct
2 Partially correct 1314 ms 63464 KB Partially correct
3 Correct 1154 ms 63340 KB Output is correct