oj.uz

Submission #715345

# Submission time Handle Problem Language Result Execution time Memory
715345 2023-03-26T14:28:58 Z Ahmed57 Hiring (IOI09_hiring) C++14
73 / 100
 851 ms 32584 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;
    while(q.size()){
        cout<<q.top().second<<"\n";
        q.pop();
    }
}

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++){
      |                   ~^~~~~

Subtask #1
22.0 / 30.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 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 2 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 7 ms 568 KB Output is correct
10 Correct 7 ms 660 KB Output is correct
11 Partially correct 9 ms 660 KB Partially correct
12 Correct 12 ms 788 KB Output is correct
13 Partially correct 12 ms 920 KB Partially correct
14 Correct 19 ms 1140 KB Output is correct
15 Partially correct 22 ms 1296 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 1 ms 212 KB Partially correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 27 ms 1720 KB Output is correct
5 Correct 85 ms 4028 KB Output is correct
6 Partially correct 476 ms 22504 KB Partially correct
7 Correct 649 ms 27400 KB Output is correct

Subtask #3
3.0 / 6.0

# 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 340 KB Output is correct

Subtask #4
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 340 KB Partially correct
2 Partially correct 2 ms 340 KB Partially correct
3 Correct 1 ms 340 KB Output is correct

Subtask #5
3.0 / 6.0

# 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

Subtask #6
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 184 ms 8164 KB Partially correct
2 Partially correct 203 ms 8100 KB Partially correct
3 Correct 190 ms 8084 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 14756 KB Output is correct
2 Correct 338 ms 14740 KB Output is correct
3 Correct 326 ms 14736 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 777 ms 31660 KB Output is correct
2 Correct 748 ms 31792 KB Output is correct
3 Correct 746 ms 31648 KB Output is correct

Subtask #9
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 851 ms 32456 KB Output is correct
2 Partially correct 840 ms 32584 KB Partially correct
3 Correct 835 ms 32552 KB Output is correct