UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#215153#2441. 物品naroto2022901876ms16764kbC++1.3kb2024-11-26 20:43:122024-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...

output:


result: