Submission #715351

# Submission time Handle Problem Language Result Execution time Memory
715351 2023-03-26T14:31:36 Z Ahmed57 Hiring (IOI09_hiring) C++17
73 / 100
830 ms 32644 KB
#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

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++){
      |                   ~^~~~~
# 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 0 ms 212 KB Partially correct
6 Correct 3 ms 340 KB Output is correct
7 Partially correct 3 ms 340 KB Partially correct
8 Partially correct 4 ms 468 KB Partially correct
9 Correct 6 ms 596 KB Output is correct
10 Correct 7 ms 680 KB Output is correct
11 Partially correct 10 ms 660 KB Partially correct
12 Correct 11 ms 716 KB Output is correct
13 Partially correct 15 ms 860 KB Partially correct
14 Correct 19 ms 1132 KB Output is correct
15 Partially correct 21 ms 1292 KB Partially correct
# 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 0 ms 212 KB Output is correct
4 Correct 28 ms 1732 KB Output is correct
5 Correct 84 ms 4108 KB Output is correct
6 Partially correct 477 ms 22440 KB Partially correct
7 Correct 646 ms 27504 KB Output is correct
# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Partially correct
2 Partially correct 1 ms 212 KB Partially correct
3 Correct 1 ms 212 KB Output is correct
# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 340 KB Partially correct
2 Partially correct 1 ms 340 KB Partially correct
3 Correct 2 ms 340 KB Output is correct
# 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
# Verdict Execution time Memory Grader output
1 Partially correct 185 ms 8072 KB Partially correct
2 Partially correct 194 ms 8052 KB Partially correct
3 Correct 183 ms 8116 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 315 ms 14780 KB Output is correct
2 Correct 318 ms 14736 KB Output is correct
3 Correct 319 ms 14740 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 750 ms 31732 KB Output is correct
2 Correct 758 ms 31744 KB Output is correct
3 Correct 743 ms 31776 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 819 ms 32644 KB Output is correct
2 Partially correct 821 ms 32432 KB Partially correct
3 Correct 830 ms 32524 KB Output is correct