# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
715370 |
2023-03-26T14:56:27 Z |
Ahmed57 |
Hiring (IOI09_hiring) |
C++14 |
|
1232 ms |
63400 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 = -1;
long double su = 0.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 = no;
}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){
| ~~~~~~~~^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
3 ms |
468 KB |
Output is correct |
7 |
Correct |
4 ms |
468 KB |
Output is correct |
8 |
Correct |
5 ms |
660 KB |
Output is correct |
9 |
Correct |
7 ms |
832 KB |
Output is correct |
10 |
Correct |
12 ms |
976 KB |
Output is correct |
11 |
Correct |
12 ms |
996 KB |
Output is correct |
12 |
Correct |
15 ms |
1232 KB |
Output is correct |
13 |
Correct |
16 ms |
1464 KB |
Output is correct |
14 |
Correct |
25 ms |
1964 KB |
Output is correct |
15 |
Correct |
27 ms |
2296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
35 ms |
3156 KB |
Output is correct |
5 |
Correct |
113 ms |
7908 KB |
Output is correct |
6 |
Correct |
645 ms |
44028 KB |
Output is correct |
7 |
Correct |
878 ms |
53732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
392 KB |
Output is correct |
3 |
Correct |
2 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
242 ms |
15740 KB |
Output is correct |
2 |
Correct |
266 ms |
15668 KB |
Output is correct |
3 |
Correct |
253 ms |
15656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
474 ms |
28972 KB |
Output is correct |
2 |
Correct |
459 ms |
28772 KB |
Output is correct |
3 |
Correct |
436 ms |
28800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1000 ms |
62120 KB |
Output is correct |
2 |
Correct |
1016 ms |
62108 KB |
Output is correct |
3 |
Correct |
1008 ms |
62032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1202 ms |
63400 KB |
Output is correct |
2 |
Correct |
1232 ms |
63372 KB |
Output is correct |
3 |
Correct |
1154 ms |
63400 KB |
Output is correct |