#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
using namespace std;
signed main(){
long long n;
double w;
cin>>n>>w;
vector<pair<double,pair<double,int>>> v;
for(int i = 0;i<n;i++){
double s,q;cin>>s>>q;
v.push_back({s/q,{q,i+1}});
}
sort(v.begin(),v.end());
priority_queue<pair<double,int>> q,p;
double sum = 0;
int 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();
double no =sum*v[i].first;
while(no>w){
pair<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();
double no =sum*v[i].first;
while(no>w){
pair<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<double, std::pair<double, 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<double, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
32 | if(q.size()>=ma){
| ~~~~~~~~^~~~
hiring.cpp:40:20: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
40 | for(int i = 0;i<=ind;i++){
| ~^~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Partially correct |
0 ms |
212 KB |
Partially correct |
3 |
Partially correct |
0 ms |
212 KB |
Partially correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Partially correct |
0 ms |
212 KB |
Partially correct |
6 |
Correct |
3 ms |
340 KB |
Output is correct |
7 |
Partially correct |
3 ms |
340 KB |
Partially correct |
8 |
Partially correct |
4 ms |
468 KB |
Partially correct |
9 |
Correct |
6 ms |
596 KB |
Output is correct |
10 |
Correct |
7 ms |
680 KB |
Output is correct |
11 |
Partially correct |
10 ms |
660 KB |
Partially correct |
12 |
Correct |
11 ms |
716 KB |
Output is correct |
13 |
Partially correct |
15 ms |
860 KB |
Partially correct |
14 |
Correct |
19 ms |
1132 KB |
Output is correct |
15 |
Partially correct |
21 ms |
1292 KB |
Partially correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Partially correct |
0 ms |
212 KB |
Partially correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
28 ms |
1732 KB |
Output is correct |
5 |
Correct |
84 ms |
4108 KB |
Output is correct |
6 |
Partially correct |
477 ms |
22440 KB |
Partially correct |
7 |
Correct |
646 ms |
27504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Partially correct |
1 ms |
212 KB |
Partially correct |
2 |
Partially correct |
1 ms |
212 KB |
Partially correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Partially correct |
2 ms |
340 KB |
Partially correct |
2 |
Partially correct |
1 ms |
340 KB |
Partially correct |
3 |
Correct |
2 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Partially correct |
185 ms |
8072 KB |
Partially correct |
2 |
Partially correct |
194 ms |
8052 KB |
Partially correct |
3 |
Correct |
183 ms |
8116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
315 ms |
14780 KB |
Output is correct |
2 |
Correct |
318 ms |
14736 KB |
Output is correct |
3 |
Correct |
319 ms |
14740 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
750 ms |
31732 KB |
Output is correct |
2 |
Correct |
758 ms |
31744 KB |
Output is correct |
3 |
Correct |
743 ms |
31776 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
819 ms |
32644 KB |
Output is correct |
2 |
Partially correct |
821 ms |
32432 KB |
Partially correct |
3 |
Correct |
830 ms |
32524 KB |
Output is correct |