#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=5e5;
struct Worker
{
long long s,q;
int id;
Worker(long long _s=0,long long _q=1,int _id=0) : s(_s), q(_q), id(_id) {};
bool operator<(const Worker &oth) const
{
return s*oth.q<oth.s*q;
}
bool operator<=(const Worker &oth) const
{
return s*oth.q<=oth.s*q;
}
};
bool comp1(Worker a,Worker b)
{
return (a.q>b.q);
}
Worker tab[N+10];
Worker tq[N+10];
int gg[N+10];
bool us[N+10];
Worker solve(int n,long long w,int mid,Worker brk)
{
for(int i=1;i<=n;i++)
us[i]=false;
Worker mn={w+1,1};
long long sum=0;
int cnt=0;
int bb=1;
for(int i=1;i<=n;i++)
{
if(cnt==mid-1)
mn=min(mn,Worker((sum+tab[i].q)*tab[i].s,tab[i].q));
if(mn.s*brk.q==mn.q*brk.s)
{
us[gg[tab[i].id]]=true;;
return mn;
}
if(cnt>=mid-1 && mid>1)
{
while(!us[bb])
bb++;
}
if(cnt<mid-1)
{
sum+=tab[i].q;
cnt++;
us[gg[tab[i].id]]=true;
}
else if(mid>1 && tab[i].q<tq[bb].q)
{
sum+=tab[i].q-tq[bb].q;
us[bb]=false;
us[gg[tab[i].id]]=true;
}
}
return mn;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
long long w;
cin>>n>>w;
for(int i=1;i<=n;i++)
{
cin>>tab[i].s>>tab[i].q;
tab[i].id=i;
tq[i]=tab[i];
}
sort(tab+1,tab+n+1);
sort(tq+1,tq+n+1,comp1);
for(int i=1;i<=n;i++)
gg[tq[i].id]=i;
int bg=0,en=n;
while(bg<en)
{
int mid=(bg+en+1)/2;
if(solve(n,w,mid,Worker(-1,1))<=Worker(w,1))
bg=mid;
else
en=mid-1;
}
cout<<bg<<"\n";
solve(n,w,bg,solve(n,w,bg,Worker(-1,1)));
for(int i=1;i<=n;i++)
{
if(us[i])
cout<<tq[i].id<<"\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23756 KB |
Output is correct |
2 |
Correct |
12 ms |
23756 KB |
Output is correct |
3 |
Correct |
12 ms |
23736 KB |
Output is correct |
4 |
Correct |
12 ms |
23772 KB |
Output is correct |
5 |
Correct |
12 ms |
23756 KB |
Output is correct |
6 |
Correct |
13 ms |
23720 KB |
Output is correct |
7 |
Correct |
13 ms |
23804 KB |
Output is correct |
8 |
Correct |
14 ms |
23744 KB |
Output is correct |
9 |
Correct |
14 ms |
23756 KB |
Output is correct |
10 |
Correct |
16 ms |
23796 KB |
Output is correct |
11 |
Correct |
16 ms |
23760 KB |
Output is correct |
12 |
Correct |
17 ms |
23764 KB |
Output is correct |
13 |
Correct |
17 ms |
23856 KB |
Output is correct |
14 |
Correct |
20 ms |
23884 KB |
Output is correct |
15 |
Correct |
21 ms |
23876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
23712 KB |
Output is correct |
2 |
Correct |
16 ms |
23756 KB |
Output is correct |
3 |
Correct |
14 ms |
23740 KB |
Output is correct |
4 |
Correct |
26 ms |
23928 KB |
Output is correct |
5 |
Correct |
52 ms |
24168 KB |
Output is correct |
6 |
Correct |
295 ms |
25908 KB |
Output is correct |
7 |
Correct |
364 ms |
26740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
23756 KB |
Output is correct |
2 |
Correct |
13 ms |
23816 KB |
Output is correct |
3 |
Correct |
14 ms |
23800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
23768 KB |
Output is correct |
2 |
Correct |
13 ms |
23808 KB |
Output is correct |
3 |
Correct |
13 ms |
23808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
23756 KB |
Output is correct |
2 |
Correct |
14 ms |
23756 KB |
Output is correct |
3 |
Correct |
14 ms |
23816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
105 ms |
24516 KB |
Output is correct |
2 |
Correct |
111 ms |
24944 KB |
Output is correct |
3 |
Correct |
108 ms |
24856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
187 ms |
25192 KB |
Output is correct |
2 |
Correct |
178 ms |
25504 KB |
Output is correct |
3 |
Correct |
176 ms |
25540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
455 ms |
27076 KB |
Output is correct |
2 |
Correct |
426 ms |
31848 KB |
Output is correct |
3 |
Correct |
458 ms |
31876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
544 ms |
27504 KB |
Output is correct |
2 |
Correct |
502 ms |
32792 KB |
Output is correct |
3 |
Correct |
510 ms |
32788 KB |
Output is correct |