Submission #715351

#	Time	Username	Problem	Language	Result	Execution time	Memory
715351		Ahmed57	Hiring (IOI09_hiring)	C++17	73 / 100	830 ms	32644 KiB

hiring

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")

using namespace std;

signed main(){
    long long n;
    double w;
    cin>>n>>w;
    vector<pair<double,pair<double,int>>> v;
    for(int i = 0;i<n;i++){
        double s,q;cin>>s>>q;
        v.push_back({s/q,{q,i+1}});
    }
    sort(v.begin(),v.end());
    priority_queue<pair<double,int>> q,p;
    double sum = 0;
    int 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();
        double no =sum*v[i].first;
        while(no>w){
            pair<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();
        double no =sum*v[i].first;
        while(no>w){
            pair<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 (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<double, std::pair<double, 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<double, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |         if(q.size()>=ma){
      |            ~~~~~~~~^~~~
hiring.cpp:40:20: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   40 |     for(int i = 0;i<=ind;i++){
      |                   ~^~~~~

• Subtask 1: 22 / 30
• Subtask 2: 24 / 28
• Subtask 3: 3 / 6
• Subtask 4: 3 / 6
• Subtask 5: 3 / 6
• Subtask 6: 3 / 6
• Subtask 7: 6 / 6
• Subtask 8: 6 / 6
• Subtask 9: 3 / 6