oj.uz

Submission #715355

# Submission time Handle Problem Language Result Execution time Memory
715355 2023-03-26T14:35:09 Z Ahmed57 Hiring (IOI09_hiring) C++14
51 / 100
 1213 ms 57236 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;
        if(no>w){
            pair<long 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();
        long double no =sum*v[i].first;
        if(no>w){
            pair<long 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: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:31: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]
   31 |         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
16.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 Partially correct 0 ms 212 KB Partially correct
4 Partially correct 0 ms 212 KB Partially correct
5 Partially correct 1 ms 212 KB Partially correct
6 Partially correct 5 ms 468 KB Partially correct
7 Partially correct 6 ms 468 KB Partially correct
8 Partially correct 6 ms 660 KB Partially correct
9 Partially correct 8 ms 788 KB Partially correct
10 Partially correct 13 ms 848 KB Partially correct
11 Partially correct 11 ms 1068 KB Partially correct
12 Partially correct 14 ms 1056 KB Partially correct
13 Partially correct 19 ms 1240 KB Partially correct
14 Partially correct 24 ms 1560 KB Partially correct
15 Partially correct 29 ms 2056 KB Partially correct

Subtask #2
14.0 / 28.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 Partially correct 1 ms 212 KB Partially correct
4 Partially correct 42 ms 2328 KB Partially correct
5 Partially correct 131 ms 7628 KB Partially correct
6 Partially correct 752 ms 32748 KB Partially correct
7 Partially correct 911 ms 40748 KB Partially correct

Subtask #3
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 340 KB Partially correct
2 Partially correct 1 ms 340 KB Partially correct
3 Partially correct 1 ms 340 KB Partially 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 Partially correct 2 ms 340 KB Partially 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 Partially correct 2 ms 340 KB Partially correct

Subtask #6
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 273 ms 14524 KB Partially correct
2 Partially correct 251 ms 14440 KB Partially correct
3 Partially correct 257 ms 14544 KB Partially correct

Subtask #7
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 446 ms 22620 KB Partially correct
2 Partially correct 444 ms 22512 KB Partially correct
3 Partially correct 440 ms 22496 KB Partially correct

Subtask #8
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 1090 ms 57084 KB Partially correct
2 Partially correct 1034 ms 57092 KB Partially correct
3 Partially correct 1047 ms 57236 KB Partially correct

Subtask #9
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 1164 ms 57188 KB Partially correct
2 Partially correct 1213 ms 57152 KB Partially correct
3 Partially correct 1142 ms 57236 KB Partially correct