oj.uz

Submission #715337

# Submission time Handle Problem Language Result Execution time Memory
715337 2023-03-26T14:21:30 Z Ahmed57 Hiring (IOI09_hiring) C++14
60 / 100
 835 ms 34816 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;
        if(no>w){
            pair<double,int>pa = q.top();
            q.pop();
            sum-=pa.first;
            p.push({-pa.first,pa.second});
        }
        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;
        if(no>w){
            pair<double,int>pa = q.top();
            q.pop();
            sum-=pa.first;
            p.push({-pa.first,pa.second});
        }
    }
    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:30: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]
   30 |         if(q.size()>ma){
      |            ~~~~~~~~^~~
hiring.cpp:38:20: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |     for(int i = 0;i<=ind;i++){
      |                   ~^~~~~

Subtask #1
19.0 / 30.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 212 KB Output is correct
4 Partially correct 1 ms 212 KB Partially correct
5 Partially correct 1 ms 212 KB Partially correct
6 Partially correct 2 ms 340 KB Partially correct
7 Partially correct 3 ms 436 KB Partially correct
8 Partially correct 4 ms 468 KB Partially correct
9 Correct 6 ms 596 KB Output is correct
10 Partially correct 7 ms 744 KB Partially correct
11 Correct 9 ms 764 KB Output is correct
12 Partially correct 10 ms 788 KB Partially correct
13 Partially correct 11 ms 900 KB Partially correct
14 Correct 18 ms 996 KB Output is correct
15 Partially correct 21 ms 1360 KB Partially correct

Subtask #2
20.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 Partially correct 27 ms 1568 KB Partially correct
5 Partially correct 84 ms 4560 KB Partially correct
6 Correct 464 ms 20012 KB Output is correct
7 Partially correct 621 ms 24968 KB Partially 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 340 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 Correct 2 ms 340 KB Output is correct
2 Partially correct 1 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 Correct 2 ms 340 KB Output is 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 187 ms 8688 KB Partially correct
2 Partially correct 187 ms 8868 KB Partially correct
3 Correct 177 ms 8692 KB Output is correct

Subtask #7
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 318 ms 13748 KB Partially correct
2 Partially correct 307 ms 13612 KB Partially correct
3 Correct 317 ms 13732 KB Output is correct

Subtask #8
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 734 ms 34100 KB Output is correct
2 Partially correct 715 ms 34180 KB Partially correct
3 Correct 711 ms 34380 KB Output is correct

Subtask #9
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 804 ms 34816 KB Output is correct
2 Partially correct 835 ms 34660 KB Partially correct
3 Correct 788 ms 34768 KB Output is correct