#include <bits/stdc++.h>
using namespace std;
#define int long long
#define forn(i,n) for(int i=0;i<n;++i)
//#define pi pair<int,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vii(a,n) vector<int>a(n);forn(i,n)cin>>a[i];
struct pi {
int f,s,i;
pi(int a, int b) {
f=a,s=b,i=0;
}
pi(){}
};
bool foo(pi a, pi b) {
return a.f*b.s < b.f*a.s;
}
void insert(vector<int>&v, int x) {
if (!v.size() || x>=v.back()) {
v.pb(x); return;
}
int i=0;
while (x>v[i]) ++i;
int t=x;
while (i<v.size()) {
int z=t;
t=v[i];
v[i]=z;
++i;
}
v.pb(t);
}
bool zzz(pi a, pi b) {
return a.f<b.f;
}
void solve() {
int n,w; cin>>n>>w;
vector<pi> a(n); forn(i,n) { cin>>a[i].f>>a[i].s; a[i].i=i;}
sort(all(a),foo);
int ans=-1, best; pi frac;
int sum=0;
priority_queue<int> q;
forn(i,n) {
sum+=a[i].s;
q.push(a[i].s);
while (sum*a[i].f > w*a[i].s) {
sum-=q.top(); q.pop();
}
if ((int)(q.size()) > ans) {
ans=q.size();
best=i;
frac = { sum*a[i].f, a[i].s };
}
if ((int)(q.size()) == ans) {
if ( sum*a[i].f*frac.s < frac.f*a[i].s ) {
best=i;
frac = { sum*a[i].f, a[i].s };
}
}
}
cout<<ans<<'\n';
vector<pi> z;
forn(i,best+1) z.pb({a[i].s,a[i].i});
sort(all(z),zzz);
sum=0;
int i=best;
vector<int> ok;
forn(j,i+1) {
int x = (sum+z[j].f)*a[i].f;
int y = a[i].s;
if (foo( {w,1}, {x,y} )) break;
sum+=z[j].f;
ok.pb(z[j].s);
}
sort(all(ok));
for(auto&x:ok) cout<<x+1<<'\n';
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
solve();
}
Compilation message
hiring.cpp: In function 'void insert(std::vector<long long int>&, long long int)':
hiring.cpp:32:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | while (i<v.size()) {
| ~^~~~~~~~~
hiring.cpp: In function 'void solve()':
hiring.cpp:83:27: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
83 | int x = (sum+z[j].f)*a[i].f;
| ^
hiring.cpp:68:35: warning: 'frac.pi::first' may be used uninitialized in this function [-Wmaybe-uninitialized]
68 | if ( sum*a[i].f*frac.s < frac.f*a[i].s ) {
| ^
hiring.cpp:68:19: warning: 'frac.pi::second' may be used uninitialized in this function [-Wmaybe-uninitialized]
68 | if ( sum*a[i].f*frac.s < frac.f*a[i].s ) {
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
320 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
656 KB |
Output is correct |
10 |
Correct |
2 ms |
596 KB |
Output is correct |
11 |
Correct |
3 ms |
916 KB |
Output is correct |
12 |
Correct |
3 ms |
964 KB |
Output is correct |
13 |
Correct |
3 ms |
704 KB |
Output is correct |
14 |
Correct |
6 ms |
1336 KB |
Output is correct |
15 |
Correct |
6 ms |
1212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
312 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
8 ms |
1464 KB |
Output is correct |
5 |
Correct |
19 ms |
3192 KB |
Output is correct |
6 |
Correct |
147 ms |
18632 KB |
Output is correct |
7 |
Correct |
176 ms |
28664 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
324 KB |
Output is correct |
2 |
Correct |
1 ms |
328 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
56 ms |
7952 KB |
Output is correct |
2 |
Correct |
55 ms |
7904 KB |
Output is correct |
3 |
Correct |
56 ms |
7900 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
82 ms |
14452 KB |
Output is correct |
2 |
Correct |
83 ms |
14400 KB |
Output is correct |
3 |
Correct |
88 ms |
14460 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
222 ms |
30808 KB |
Output is correct |
2 |
Correct |
228 ms |
30832 KB |
Output is correct |
3 |
Correct |
226 ms |
30812 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
252 ms |
33340 KB |
Output is correct |
2 |
Correct |
253 ms |
33352 KB |
Output is correct |
3 |
Correct |
263 ms |
33576 KB |
Output is correct |