oj.uz

Submission #715354

# Submission time Handle Problem Language Result Execution time Memory
715354 2023-03-26T14:34:09 Z Ahmed57 Hiring (IOI09_hiring) C++14
60 / 100
 1242 ms 63552 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
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 1 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 3 ms 468 KB Partially correct
8 Partially correct 5 ms 660 KB Partially correct
9 Correct 8 ms 848 KB Output is correct
10 Partially correct 9 ms 976 KB Partially correct
11 Correct 11 ms 996 KB Output is correct
12 Partially correct 14 ms 1240 KB Partially correct
13 Partially correct 16 ms 1464 KB Partially correct
14 Correct 29 ms 1948 KB Output is correct
15 Partially correct 29 ms 2252 KB Partially correct

Subtask #2
20.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 Partially correct 36 ms 3132 KB Partially correct
5 Partially correct 108 ms 7816 KB Partially correct
6 Correct 683 ms 44032 KB Output is correct
7 Partially correct 893 ms 53948 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 2 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 1 ms 340 KB Output is correct
2 Partially correct 2 ms 340 KB Partially correct
3 Correct 2 ms 392 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 3 ms 340 KB Output is correct

Subtask #6
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 287 ms 15676 KB Partially correct
2 Partially correct 256 ms 15788 KB Partially correct
3 Correct 267 ms 15752 KB Output is correct

Subtask #7
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 454 ms 28868 KB Partially correct
2 Partially correct 467 ms 28808 KB Partially correct
3 Correct 481 ms 28960 KB Output is correct

Subtask #8
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1052 ms 62112 KB Output is correct
2 Partially correct 1058 ms 62108 KB Partially correct
3 Correct 1018 ms 62152 KB Output is correct

Subtask #9
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1153 ms 63552 KB Output is correct
2 Partially correct 1242 ms 63356 KB Partially correct
3 Correct 1179 ms 63512 KB Output is correct