oj.uz

Submission #715360

# Submission time Handle Problem Language Result Execution time Memory
715360 2023-03-26T14:41:55 Z Ahmed57 Hiring (IOI09_hiring) C++14
60 / 100
 1191 ms 63420 KB 
#include <bits/stdc++.h>

using namespace std;

signed main(){
    long long n;
    long long w;
    cin>>n>>w;
    vector<pair<long double,pair<long double,long long>>> v;
    for(int i = 0;i<n;i++){
        long double s,q;cin>>s>>q;
        v.push_back({s/q,{q,i+1}});
    }
    sort(v.begin(),v.end());
    priority_queue<pair<long double,int>> q,p;
    long double sum = 0;
    long long ma = 0,ind;
    long double su = 1000000000.0;
    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();
        long double no =sum*v[i].first;
        while(no>w){
            pair<long 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;
        }if(q.size()==ma&&su>no){
            su = no;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();
        long double no =sum*v[i].first;
        while(no>w){
            pair<long 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<long double, std::pair<long double, long long 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<long double, int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   32 |         if(q.size()>ma){
      |            ~~~~~~~~^~~
hiring.cpp:35:21: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<long double, int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   35 |         }if(q.size()==ma&&su>no){
      |             ~~~~~~~~^~~~
hiring.cpp:17:22: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   17 |     long long ma = 0,ind;
      |                      ^~~

Subtask #1
19.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Partially correct
2 Partially correct 1 ms 212 KB Partially correct
3 Correct 0 ms 212 KB Output is correct
4 Partially correct 0 ms 212 KB Partially correct
5 Partially correct 1 ms 212 KB Partially correct
6 Partially correct 3 ms 468 KB Partially correct
7 Partially correct 4 ms 468 KB Partially correct
8 Partially correct 5 ms 700 KB Partially correct
9 Correct 8 ms 836 KB Output is correct
10 Partially correct 10 ms 976 KB Partially correct
11 Correct 13 ms 976 KB Output is correct
12 Partially correct 14 ms 1232 KB Partially correct
13 Partially correct 17 ms 1588 KB Partially correct
14 Correct 28 ms 1968 KB Output is correct
15 Partially correct 27 ms 2264 KB Partially correct

Subtask #2
20.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 1 ms 212 KB Output is correct
4 Partially correct 35 ms 3184 KB Partially correct
5 Partially correct 106 ms 7968 KB Partially correct
6 Correct 677 ms 44120 KB Output is correct
7 Partially correct 947 ms 53892 KB Partially correct

Subtask #3
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 356 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 2 ms 340 KB Partially correct
3 Correct 2 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 248 ms 15740 KB Partially correct
2 Partially correct 247 ms 15844 KB Partially correct
3 Correct 278 ms 15756 KB Output is correct

Subtask #7
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 441 ms 28808 KB Partially correct
2 Partially correct 450 ms 28908 KB Partially correct
3 Correct 448 ms 28836 KB Output is correct

Subtask #8
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1010 ms 62180 KB Output is correct
2 Partially correct 1012 ms 62104 KB Partially correct
3 Correct 1022 ms 62032 KB Output is correct

Subtask #9
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1148 ms 63420 KB Output is correct
2 Partially correct 1191 ms 63376 KB Partially correct
3 Correct 1147 ms 63340 KB Output is correct