QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#552546 | #9252. Penguins in Refrigerator | ucup-team4504# | TL | 723ms | 118672kb | C++14 | 1.3kb | 2024-09-07 23:39:43 | 2024-09-07 23:39:43 |
Judging History
answer
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7, inf = 1e9 + 1;
int n, w, ans;
int a[N], p[N], pos[N];
int mx[N];
int m, p2[N];
pair<int, int> b[N];
set<int> st[N];
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("in.txt", "r", stdin);
// freopen("out2.txt", "w", stdout);
ans = 1;
cin >> n >> w;
for (int i = 1; i <= n; i++) cin >> p[i];
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++)
if (a[p[i]] * 2 > w) p2[++m] = p[i];
else pos[p[i]] = m;
for (int i = 1; i <= n; i++) b[i] = make_pair(a[i], i);
a[0] = inf;
for (int i = 0; i <= m; i++) mx[i] = p2[i];
sort(b + 1, b + 1 + n);
for (int i = n; i >= 1; i--)
if (b[i].first * 2 <= w){
int j = b[i].second;
int l = pos[j], r = pos[j] + 1;
while (l && a[p2[l]] + a[j] <= w) l--;
while (r <= m && a[p2[r]] + a[j] <= w) r++;
int sz = r - l;
for (int j = l; j < r; j++) sz += st[j].size();
ans = 1ll * ans * sz % mod;
int t = r - 1;
while (t > l && mx[t] < j) t--;
st[t].insert(j);
mx[t] = max({j, mx[t], p2[t]});
}
cout << ans << endl;
for (int i = m; i >= 1; i--){
for (int x : st[i]) cout << x << ' ';
cout << p2[i] << ' ';
}
for (int x : st[0]) cout << x << ' ';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 60356kb
input:
5 10 1 2 3 4 5 6 5 3 9 2
output:
3 5 4 2 1 3
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 7ms
memory: 60136kb
input:
5 10 1 2 3 4 5 2 4 3 3 8
output:
30 1 5 2 3 4
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 4ms
memory: 56872kb
input:
5 10 1 2 3 4 5 2 3 4 5 1
output:
120 1 2 3 4 5
result:
ok 2 lines
Test #4:
score: 0
Accepted
time: 7ms
memory: 59944kb
input:
5 10 1 2 3 4 5 2 3 4 5 6
output:
60 1 2 3 5 4
result:
ok 2 lines
Test #5:
score: 0
Accepted
time: 41ms
memory: 66904kb
input:
100000 96 1996 78922 45321 68844 32404 82013 66552 81163 17216 48170 35495 56660 13480 43118 23173 47257 50168 87069 26167 67231 31758 25694 61063 56642 8923 7727 54528 96554 38964 7604 6822 16256 45300 58869 31359 48638 87645 14779 81505 59585 89293 9291 7002 31810 84701 77648 78295 42595 11394 479...
output:
457992974 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...
result:
ok 2 lines
Test #6:
score: 0
Accepted
time: 44ms
memory: 68340kb
input:
100000 84 93330 3894 94859 22134 49668 30606 26739 82976 76701 56323 75537 7626 87226 20857 98177 21811 70827 75898 8111 48223 26186 64222 63002 79024 19126 41638 1048 43857 25379 19764 60207 27675 77665 66327 6274 34861 30287 13449 64505 51490 5804 65843 49014 85795 12365 31565 34411 71697 66568 28...
output:
524727018 1723 2800 15421 26278 31659 42502 42606 56945 60694 62369 70160 73990 80586 88502 89122 59690 27661 33622 94788 14089 1146 2690 3632 4491 5439 8588 17476 17922 18136 20123 24857 39523 18825 28520 30999 32947 36013 41413 43842 43919 54502 58104 60783 65767 69064 71878 74728 75343 76546 7807...
result:
ok 2 lines
Test #7:
score: 0
Accepted
time: 34ms
memory: 66640kb
input:
100000 87 300 88662 44078 62834 3753 7407 33249 23452 84415 76976 83633 97611 16701 2788 75559 56876 65161 78422 41095 40238 89019 95291 81242 34629 35820 2766 266 62909 53458 60609 92867 7751 43644 89656 46268 73554 29490 91474 42521 66646 22973 36675 3527 66659 6283 65870 56067 93748 94932 45445 3...
output:
474454223 16291 67920 66350 36657 80297 50836 75962 67504 74275 82684 44748 18794 20817 23451 67820 94633 35098 26272 62387 64130 97543 95388 6171 41925 9995 21720 51796 81891 29780 53247 63390 78398 10287 31830 44454 46864 63394 76771 87042 17437 8412 58246 18774 97383 36854 4632 32575 64180 48940 ...
result:
ok 2 lines
Test #8:
score: 0
Accepted
time: 24ms
memory: 62632kb
input:
100000 100 55629 14377 79945 51098 90204 3853 3177 32017 78776 91382 20382 74435 13483 67713 43513 69929 15961 6388 48752 94868 14114 90543 87776 22290 94148 14665 67822 15542 37889 31214 53405 58817 74349 80153 50913 24099 84889 86056 59976 40327 59231 97231 45030 99883 57171 7168 60283 46638 6697 ...
output:
12361691 68929 26283 16078 8426 80994 89031 90845 85691 11489 83714 218 43955 79942 49055 15944 46958 3923 50718 51881 87716 91070 33513 46064 56932 23620 95805 36252 61014 77254 96568 40681 51389 15855 70350 42900 63333 35239 73615 3271 20950 31494 86984 66093 18145 50335 78044 93515 60899 73400 82...
result:
ok 2 lines
Test #9:
score: 0
Accepted
time: 199ms
memory: 75764kb
input:
1000000 81 505338 916424 583795 203566 617115 482998 227468 356473 312485 334132 3363 907091 837133 257003 855999 78795 363135 170084 379933 348671 686 989733 970073 613993 760088 594394 96392 386305 559944 490393 934509 798454 875291 431076 978853 472290 445607 906742 260667 85265 928267 662293 850...
output:
1 434417 227927 721379 881382 991471 289735 100004 760754 181792 283705 493486 797104 785634 77915 488388 580313 676447 601952 699628 15819 730688 550717 818459 115930 718996 87059 278519 341770 205766 196170 470043 729232 605060 297713 562576 502884 205091 63073 969512 719434 832742 262524 893809 1...
result:
ok 2 lines
Test #10:
score: 0
Accepted
time: 723ms
memory: 118672kb
input:
1000000 855853371 671882 962935 236810 309323 731542 936655 349551 915671 728370 235701 940712 512459 431213 624267 374020 458688 149286 146845 938189 496488 78945 50430 630392 695360 119964 195349 284330 320026 415129 675618 454235 401145 366361 129120 527400 159031 540788 688684 238547 914676 4502...
output:
641102369 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...
result:
ok 2 lines
Test #11:
score: 0
Accepted
time: 546ms
memory: 113828kb
input:
1000000 957571370 997755 236289 938217 183949 245742 901546 815337 293623 483897 447597 648079 8259 601800 328449 705646 550681 971772 635040 983132 321434 297617 994716 277334 407243 7535 441861 630008 322245 4749 622934 40122 595912 610078 418322 792502 659098 981324 115306 196723 995928 653988 12...
output:
196613543 8666 50188 54027 60170 63101 84940 100746 141072 144773 162176 166539 180410 188742 200350 233463 289011 294968 327822 361963 362045 365360 373782 378529 384683 395814 400565 412249 426607 451013 453497 486792 500299 501563 503029 527962 532266 540692 549841 554433 555692 578207 587245 309...
result:
ok 2 lines
Test #12:
score: 0
Accepted
time: 402ms
memory: 99824kb
input:
1000000 808170131 271560 789245 8943 714638 700264 418823 975445 476711 934265 77678 944870 858155 812771 462154 715736 742621 689488 193610 115853 883249 687845 531685 22131 29384 772945 176972 630084 675971 609450 488597 55786 781720 208081 97123 810367 722365 957655 302332 328957 621208 772189 13...
output:
895770364 317901 376287 641310 859340 960574 246282 32177 63684 239374 534359 591735 937287 666444 303601 764716 947219 395979 508421 750441 254676 911202 958056 390533 229585 58162 164836 431844 141305 315803 837011 504379 224738 955205 725934 375706 607486 356819 809721 739670 841619 94497 132028 ...
result:
ok 2 lines
Test #13:
score: 0
Accepted
time: 297ms
memory: 86672kb
input:
1000000 921697697 510869 325175 912287 76200 267946 196566 280254 478297 605706 422740 294586 757231 806399 421000 946945 826982 892384 94539 164635 669191 29701 283479 197248 916663 922217 873836 641086 135377 885683 938021 917652 415210 386341 909867 104726 417411 584785 221653 310404 785946 50749...
output:
26397744 74052 75686 286379 558067 712866 718029 252642 343310 883971 933200 675850 374677 702925 390886 401806 477880 946457 507454 556609 989214 824674 229271 993468 83455 325821 841962 264526 937152 604811 350821 64736 839110 135921 138196 177501 182090 302505 432962 394141 130562 190620 673567 6...
result:
ok 2 lines
Test #14:
score: 0
Accepted
time: 204ms
memory: 75824kb
input:
1000000 715224327 142757 848503 196089 967433 276363 163311 39090 467040 906998 624415 676126 894650 38094 559122 446718 948581 878403 60954 92732 411351 351153 714086 588966 236003 874560 356838 655429 454326 560887 554779 336553 360512 278255 146227 122609 258837 216395 166347 171148 428705 503848...
output:
1 725711 716862 11272 806976 86234 607909 475197 584372 220750 864835 838750 461136 764052 271663 669608 748849 409237 373833 186301 795042 393152 944766 681020 322478 634634 83655 132769 255523 171009 76865 331567 528132 604856 695065 448208 571548 792572 672111 366853 662995 271629 290686 208575 6...
result:
ok 2 lines
Test #15:
score: -100
Time Limit Exceeded
input:
1000000 94 732832 824385 80610 86380 900983 71723 382380 222054 46533 243003 730000 214251 629211 759027 143920 743196 524310 386215 709124 626379 243508 147769 169616 933797 641552 946395 522265 454896 746806 938530 413949 141576 266714 374723 1495 258 168689 853795 224890 348364 423101 547355 5811...