oj.uz

Submission #715362

# Submission time Handle Problem Language Result Execution time Memory
715362 2023-03-26T14:42:50 Z Ahmed57 Hiring (IOI09_hiring) C++14
72 / 100
 1195 ms 63520 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;
            su = sum;
        }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:36: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]
   36 |         }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
24.0 / 30.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 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 Correct 5 ms 528 KB Output is correct
7 Correct 7 ms 468 KB Output is correct
8 Correct 6 ms 660 KB Output is correct
9 Correct 8 ms 848 KB Output is correct
10 Partially correct 10 ms 1048 KB Partially correct
11 Correct 13 ms 1068 KB Output is correct
12 Partially correct 14 ms 1232 KB Partially correct
13 Correct 16 ms 1676 KB Output is correct
14 Correct 26 ms 2000 KB Output is correct
15 Partially correct 30 ms 2216 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 36 ms 3172 KB Output is correct
5 Correct 107 ms 7896 KB Output is correct
6 Correct 664 ms 44076 KB Output is correct
7 Partially correct 962 ms 53876 KB Partially correct

Subtask #3
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 #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is 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 255 ms 15704 KB Partially correct
2 Partially correct 261 ms 15720 KB Partially correct
3 Correct 270 ms 15908 KB Output is correct

Subtask #7
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 446 ms 28984 KB Partially correct
2 Partially correct 460 ms 28804 KB Partially correct
3 Correct 437 ms 28804 KB Output is correct

Subtask #8
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1037 ms 62224 KB Output is correct
2 Partially correct 1084 ms 62076 KB Partially correct
3 Correct 1052 ms 62160 KB Output is correct

Subtask #9
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1195 ms 63520 KB Output is correct
2 Partially correct 1164 ms 63316 KB Partially correct
3 Correct 1171 ms 63332 KB Output is correct