Submission #715367

#	Time	Username	Problem	Language	Result	Execution time	Memory
715367		Ahmed57	Hiring (IOI09_hiring)	C++14	72 / 100	1314 ms	63440 KiB

hiring

#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 (stderr)

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 / 30
• Subtask 2: 24 / 28
• Subtask 3: 3 / 6
• Subtask 4: 6 / 6
• Subtask 5: 3 / 6
• Subtask 6: 3 / 6
• Subtask 7: 3 / 6
• Subtask 8: 3 / 6
• Subtask 9: 3 / 6