oj.uz

Submission #715353

# Submission time Handle Problem Language Result Execution time Memory
715353 2023-03-26T14:33:17 Z Ahmed57 Hiring (IOI09_hiring) C++14
73 / 100
 1233 ms 63488 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;
    long double 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;
    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;
        }
    }
    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:18:22: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   18 |     long long ma = 0,ind;
      |                      ^~~

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 1 ms 212 KB Partially correct
4 Correct 1 ms 212 KB Output is correct
5 Partially correct 1 ms 212 KB Partially correct
6 Correct 3 ms 468 KB Output is correct
7 Partially correct 5 ms 468 KB Partially correct
8 Partially correct 5 ms 660 KB Partially correct
9 Correct 10 ms 848 KB Output is correct
10 Correct 11 ms 968 KB Output is correct
11 Partially correct 13 ms 1056 KB Partially correct
12 Correct 14 ms 1212 KB Output is correct
13 Partially correct 17 ms 1544 KB Partially correct
14 Correct 24 ms 1944 KB Output is correct
15 Partially correct 29 ms 2260 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 38 ms 3164 KB Output is correct
5 Correct 114 ms 7884 KB Output is correct
6 Partially correct 692 ms 44048 KB Partially correct
7 Correct 899 ms 53616 KB Output is 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
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 #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 264 ms 15832 KB Partially correct
2 Partially correct 249 ms 15728 KB Partially correct
3 Correct 245 ms 15668 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 28808 KB Output is correct
2 Correct 456 ms 29020 KB Output is correct
3 Correct 440 ms 28808 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1014 ms 62068 KB Output is correct
2 Correct 1034 ms 62020 KB Output is correct
3 Correct 1058 ms 62212 KB Output is correct

Subtask #9
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1197 ms 63412 KB Output is correct
2 Partially correct 1233 ms 63488 KB Partially correct
3 Correct 1171 ms 63412 KB Output is correct