oj.uz

Submission #715367

# Submission time Handle Problem Language Result Execution time Memory
715367 2023-03-26T14:49:34 Z Ahmed57 Hiring (IOI09_hiring) C++14
72 / 100
 1314 ms 63440 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});
        while(p.size()){
        sum+=(-p.top().first);
        q.push({-p.top().first,p.top().second});
        p.pop();
        long double no =sum*v[i].first;
        bool bb = 0;
        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;
            bb = 1;
        }
        if(bb)break;
        }
        if(q.size()>ma){
            ma=q.size();
            ind = i;
            su = sum;
        }if(q.size()==ma&&su>(sum*v[i].first)){
            su = (sum*v[i].first);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});
        while(p.size()){
        sum+=(-p.top().first);
        q.push({-p.top().first,p.top().second});
        p.pop();
        long double no =sum*v[i].first;
        bool bb = 0;
        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;
            bb = 1;
        }
        if(bb)break;
        }
    }
    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:37: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]
   37 |         if(q.size()>ma){
      |            ~~~~~~~~^~~
hiring.cpp:41: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]
   41 |         }if(q.size()==ma&&su>(sum*v[i].first)){
      |             ~~~~~~~~^~~~

Subtask #1
24.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Partially correct 0 ms 212 KB Partially correct
5 Partially correct 0 ms 212 KB Partially correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 5 ms 660 KB Output is correct
9 Correct 8 ms 788 KB Output is correct
10 Partially correct 10 ms 976 KB Partially correct
11 Correct 13 ms 1028 KB Output is correct
12 Partially correct 14 ms 1272 KB Partially correct
13 Correct 19 ms 1568 KB Output is correct
14 Correct 31 ms 1920 KB Output is correct
15 Partially correct 28 ms 2252 KB Partially correct

Subtask #2
24.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Partially correct 0 ms 212 KB Partially correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 38 ms 3144 KB Output is correct
5 Correct 119 ms 7872 KB Output is correct
6 Correct 728 ms 43952 KB Output is correct
7 Partially correct 1000 ms 53680 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 3 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 274 ms 15716 KB Partially correct
2 Partially correct 282 ms 15772 KB Partially correct
3 Correct 280 ms 15664 KB Output is correct

Subtask #7
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 549 ms 28816 KB Partially correct
2 Partially correct 506 ms 28816 KB Partially correct
3 Correct 485 ms 28844 KB Output is correct

Subtask #8
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1108 ms 62200 KB Output is correct
2 Partially correct 1081 ms 62136 KB Partially correct
3 Correct 1136 ms 62136 KB Output is correct

Subtask #9
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1314 ms 63336 KB Output is correct
2 Partially correct 1298 ms 63440 KB Partially correct
3 Correct 1224 ms 63392 KB Output is correct