Submission #715342

# Submission time Handle Problem Language Result Execution time Memory
715342 2023-03-26T14:26:33 Z Ahmed57 Hiring (IOI09_hiring) C++14
73 / 100
871 ms 32580 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,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;
    vector<int>ans;
    while(q.size()){
        ans.push_back(q.top().second);
        q.pop();
    }
    sort(ans.begin(),ans.end());
    for(auto i:ans)cout<<i<<"\n";
}

Compilation message

hiring.cpp: In function 'int main()':
hiring.cpp:18: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]
   18 |     for(int i = 0;i<v.size();i++){
      |                   ~^~~~~~~~~
hiring.cpp:31: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]
   31 |         if(q.size()>=ma){
      |            ~~~~~~~~^~~~
hiring.cpp:39:20: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   39 |     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 6 ms 468 KB Partially correct
9 Correct 6 ms 596 KB Output is correct
10 Correct 8 ms 640 KB Output is correct
11 Partially correct 9 ms 660 KB Partially correct
12 Correct 10 ms 752 KB Output is correct
13 Partially correct 12 ms 936 KB Partially correct
14 Correct 19 ms 1132 KB Output is correct
15 Partially correct 28 ms 1304 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 29 ms 1712 KB Output is correct
5 Correct 85 ms 4092 KB Output is correct
6 Partially correct 512 ms 22560 KB Partially correct
7 Correct 643 ms 27400 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 232 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 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 195 ms 8128 KB Partially correct
2 Partially correct 201 ms 8088 KB Partially correct
3 Correct 182 ms 8108 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 367 ms 14744 KB Output is correct
2 Correct 319 ms 14804 KB Output is correct
3 Correct 335 ms 14740 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 769 ms 31780 KB Output is correct
2 Correct 784 ms 31772 KB Output is correct
3 Correct 793 ms 31732 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 870 ms 32580 KB Output is correct
2 Partially correct 851 ms 32516 KB Partially correct
3 Correct 871 ms 32456 KB Output is correct