ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#215153 | #2441. 物品 | naroto2022 | 90 | 1876ms | 16764kb | C++ | 1.3kb | 2024-11-26 20:43:12 | 2024-11-26 23:04:38 |
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
const int MN=5e5+5;
ll n,c,p[MN];
struct node{ll a,w,id;}q[MN];
void write(ll n){if(n<0){putchar('-');write(-n);return;}if(n>9)write(n/10);putchar(n%10+'0');}
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
bool cmpa(node x, node y){return x.a==y.a?x.w<y.w:x.a<y.a;}
bool cmpw(node x, node y){return x.w==y.w?x.a<y.a:x.w<y.w;}
bool check(ll x){
if(n-p[x]+1<x) return false;
sort(q+1+p[x],q+1+n,cmpw);
ll num=0;
for(int i=p[x],j=1; j<=x; i++,j++) num+=q[i].w;
sort(q+1+p[x],q+1+n,cmpa);
return num<=c;
}
void print(ll x){
sort(q+1+p[x],q+1+n,cmpw);
for(int i=p[x],j=1; j<=x; i++,j++) write(q[i].id),putchar(' ');
putchar('\n');
}
int main(){
n=read();c=read();
for(int i=1; i<=n; i++) q[i].a=read(),q[i].w=read(),q[i].id=i;
sort(q+1,q+1+n,cmpa);
for(int i=min(1ll*500000,n),j=n; i>=1; i--){
while(q[j].a>=i) j--;
p[i]=j+1;
}
ll l=0,r=n;
while(l<=r){
ll mid=l+r>>1;
if(check(mid)) l=mid+1;
else r=mid-1;
}
write(r);putchar('\n');write(r);putchar('\n');print(l-1);
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1152kb
input:
18 1024 8 3 8 1 16 9 17 6 2 5 12 3 1 7 7 9 17 1 14 3 2 7 17 5 2 3 2 5 2 10 8 3 2 3 17 5
output:
8 8 2 9 16 1 6 10 12 18
result:
points 1.0 Correct
Test #2:
score: 10
Accepted
time: 0ms
memory: 1152kb
input:
20 79841 15 4337 9 6289 7 9927 12 1468 7 9390 12 9228 7 5646 8 3438 3 1614 3 7048 10 8840 15 2349 16...
output:
10 10 20 4 12 14 1 13 19 11 6 17
result:
points 1.0 Correct
Test #3:
score: 10
Accepted
time: 0ms
memory: 1212kb
input:
1888 987654 1082 243 1341 309 1524 959 324 593 894 952 1428 587 1367 91 1669 683 616 866 958 791 172...
output:
949 949 804 909 1341 231 1327 1259 335 892 873 1671 1070 1872 452 339 501 258 1027 793 1067 1740 665...
result:
points 1.0 Correct
Test #4:
score: 10
Accepted
time: 3ms
memory: 1208kb
input:
1999 12000000 1112 2799 524 6890 686 6713 1803 4478 940 4341 1391 8972 953 592 454 7711 524 8224 127...
output:
978 978 1806 53 174 195 1092 1807 517 789 1823 1014 991 423 1060 1800 350 1484 769 1428 1739 704 795...
result:
points 1.0 Correct
Test #5:
score: 10
Accepted
time: 3ms
memory: 1212kb
input:
2000 9788123 296 3976 154 3441 78 9146 1443 6444 1799 2843 1482 6843 1526 3159 1956 9324 1442 1001 5...
output:
997 997 1702 725 67 1669 1837 1146 694 38 223 1735 1651 1228 358 1005 811 1395 1180 1094 1150 1697 1...
result:
points 1.0 Correct
Test #6:
score: 10
Accepted
time: 262ms
memory: 7396kb
input:
200000 87654321 33240 503 90721 868 64272 858 170928 616 92246 213 50575 59 148252 954 87639 739 328...
output:
100168 100168 156597 8750 157196 75818 195251 120207 80351 137190 168288 19174 70822 122498 9544 119...
result:
points 1.0 Correct
Test #7:
score: 10
Accepted
time: 420ms
memory: 7396kb
input:
200000 987654321 199051 7573 6332 5631 35615 9816 185684 9227 198894 8029 185684 2173 54203 2887 107...
output:
98978 98978 30588 96841 42096 30257 130989 162221 74944 134505 198760 23020 89131 105487 59838 93703...
result:
points 1.0 Correct
Test #8:
score: 10
Accepted
time: 550ms
memory: 15040kb
input:
444444 998244353 243276 2272 436596 1761 70822 1547 263965 942 280972 2658 87160 421 268504 2945 103...
output:
222615 222615 72064 386384 67770 346487 158080 323946 18744 176477 241797 46580 19606 152627 309717 ...
result:
points 1.0 Correct
Test #9:
score: 10
Accepted
time: 638ms
memory: 16764kb
input:
500000 999999999 131412 807 486292 804 462352 1139 52896 196 426775 1655 18059 2099 224414 1308 2851...
output:
254580 254580 13189 6349 484675 20828 252716 114628 12307 87967 348464 35673 192611 236769 270254 28...
result:
points 1.0 Correct
Test #10:
score: 0
Time Limit Exceeded
input:
500000 1000000000 42362 5090 327916 7618 221602 679 295161 1419 69703 4221 108614 6788 210597 6940 2...