oj.uz

Submission #715349

# Submission time Handle Problem Language Result Execution time Memory
715349 2023-03-26T14:30:37 Z Ahmed57 Hiring (IOI09_hiring) C++14
73 / 100
 826 ms 32656 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++){
      |                   ~^~~~~

Subtask #1
22.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Partially correct 1 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 1 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 3 ms 468 KB Partially correct
9 Correct 7 ms 572 KB Output is correct
10 Correct 7 ms 660 KB Output is correct
11 Partially correct 10 ms 660 KB Partially correct
12 Correct 11 ms 748 KB Output is correct
13 Partially correct 12 ms 848 KB Partially correct
14 Correct 18 ms 1104 KB Output is correct
15 Partially correct 22 ms 1232 KB Partially correct

Subtask #2
24.0 / 28.0

# 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 Correct 0 ms 212 KB Output is correct
4 Correct 27 ms 1740 KB Output is correct
5 Correct 87 ms 4036 KB Output is correct
6 Partially correct 486 ms 22468 KB Partially correct
7 Correct 639 ms 27440 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 212 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 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 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 188 ms 8072 KB Partially correct
2 Partially correct 180 ms 8072 KB Partially correct
3 Correct 179 ms 8120 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 14784 KB Output is correct
2 Correct 322 ms 14732 KB Output is correct
3 Correct 321 ms 14880 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 748 ms 31704 KB Output is correct
2 Correct 734 ms 31748 KB Output is correct
3 Correct 736 ms 31660 KB Output is correct

Subtask #9
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 826 ms 32464 KB Output is correct
2 Partially correct 812 ms 32488 KB Partially correct
3 Correct 814 ms 32656 KB Output is correct