4593 - NOIP CSP 2021 普及: 第四题 小熊的果篮（fruit）

小熊的水果店里摆放着一排 n 个水果。每个水果只可能是苹果或桔子，从左到右依次用正整数 1、2、3、……、n 编号。连续排在一起的同一种水果称为一个“块”。小熊要把这一排水果挑到若干个果篮里，具体方法是：每次都把每一个“块”中最左边的水果同时挑出，组成一个果篮。重复这一操作，直至水果用完。注意，每次挑完一个果篮后，“块”可能会发生变化。比如两个苹果“块”之间的唯一桔子被挑走后，两个苹果“块”就变成了一个“块”。请帮小熊计算每个果篮里包含的水果。

输入

输入的第一行包含一个正整数 n，表示水果的数量。 输入的第二行包含 n 个空格分隔的整数，其中第 i 个数表示编号为 i 的水果的种类，1 代表苹果，0 代表桔子

输出

输出若干行。 第 i 行表示第 i 次挑出的水果组成的果篮。从小到大排序输出该果篮中所有水果的编号，每两个编号之间用一个空格分隔。

样例

输入

12
1 1 0 0 1 1 1 0 1 1 0 0

输出

1 3 5 8 9 11
2 4 6 12
7
10

输入

20
1 1 1 1 0 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0

输出

1 5 8 11 13 14 15 17
2 6 9 12 16 18
3 7 10 19
4 20

输入

1000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0

输出

1 52 53 98 99 100 118 119 168 169 200 300 400 409 410 500 600 656 657 700 771 772 800 823 824 862 863 900 969 970 1000
2 101 201 301 401 501 601 701 801 901
3 102 202 302 402 502 602 702 802 902
4 103 203 303 403 503 603 703 803 903
5 104 204 304 404 504 604 704 804 904
6 105 205 305 405 505 605 705 805 905
7 106 206 306 406 506 606 706 806 906
8 107 207 307 407 507 607 707 807 907
9 108 208 308 408 508 608 708 808 908
10 109 209 309 411 509 609 709 809 909
11 110 210 310 412 510 610 710 810 910
12 111 211 311 413 511 611 711 811 911
13 112 212 312 414 512 612 712 812 912
14 113 213 313 415 513 613 713 813 913
15 114 214 314 416 514 614 714 814 914
16 115 215 315 417 515 615 715 815 915
17 116 216 316 418 516 616 716 816 916
18 117 217 317 419 517 617 717 817 917
19 120 218 318 420 518 618 718 818 918
20 121 219 319 421 519 619 719 819 919
21 122 220 320 422 520 620 720 820 920
22 123 221 321 423 521 621 721 821 921
23 124 222 322 424 522 622 722 822 922
24 125 223 323 425 523 623 723 825 923
25 126 224 324 426 524 624 724 826 924
26 127 225 325 427 525 625 725 827 925
27 128 226 326 428 526 626 726 828 926
28 129 227 327 429 527 627 727 829 927
29 130 228 328 430 528 628 728 830 928
30 131 229 329 431 529 629 729 831 929
31 132 230 330 432 530 630 730 832 930
32 133 231 331 433 531 631 731 833 931
33 134 232 332 434 532 632 732 834 932
34 135 233 333 435 533 633 733 835 933
35 136 234 334 436 534 634 734 836 934
36 137 235 335 437 535 635 735 837 935
37 138 236 336 438 536 636 736 838 936
38 139 237 337 439 537 637 737 839 937
39 140 238 338 440 538 638 738 840 938
40 141 239 339 441 539 639 739 841 939
41 142 240 340 442 540 640 740 842 940
42 143 241 341 443 541 641 741 843 941
43 144 242 342 444 542 642 742 844 942
44 145 243 343 445 543 643 743 845 943
45 146 244 344 446 544 644 744 846 944
46 147 245 345 447 545 645 745 847 945
47 148 246 346 448 546 646 746 848 946
48 149 247 347 449 547 647 747 849 947
49 150 248 348 450 548 648 748 850 948
50 151 249 349 451 549 649 749 851 949
51 152 250 350 452 550 650 750 852 950
54 153 251 351 453 551 651 751 853 951
55 154 252 352 454 552 652 752 854 952
56 155 253 353 455 553 653 753 855 953
57 156 254 354 456 554 654 754 856 954
58 157 255 355 457 555 655 755 857 955
59 158 256 356 458 556 658 756 858 956
60 159 257 357 459 557 659 757 859 957
61 160 258 358 460 558 660 758 860 958
62 161 259 359 461 559 661 759 861 959
63 162 260 360 462 560 662 760 864 960
64 163 261 361 463 561 663 761 865 961
65 164 262 362 464 562 664 762 866 962
66 165 263 363 465 563 665 763 867 963
67 166 264 364 466 564 666 764 868 964
68 167 265 365 467 565 667 765 869 965
69 170 266 366 468 566 668 766 870 966
70 171 267 367 469 567 669 767 871 967
71 172 268 368 470 568 670 768 872 968
72 173 269 369 471 569 671 769 873 971
73 174 270 370 472 570 672 770 874 972
74 175 271 371 473 571 673 773 875 973
75 176 272 372 474 572 674 774 876 974
76 177 273 373 475 573 675 775 877 975
77 178 274 374 476 574 676 776 878 976
78 179 275 375 477 575 677 777 879 977
79 180 276 376 478 576 678 778 880 978
80 181 277 377 479 577 679 779 881 979
81 182 278 378 480 578 680 780 882 980
82 183 279 379 481 579 681 781 883 981
83 184 280 380 482 580 682 782 884 982
84 185 281 381 483 581 683 783 885 983
85 186 282 382 484 582 684 784 886 984
86 187 283 383 485 583 685 785 887 985
87 188 284 384 486 584 686 786 888 986
88 189 285 385 487 585 687 787 889 987
89 190 286 386 488 586 688 788 890 988
90 191 287 387 489 587 689 789 891 989
91 192 288 388 490 588 690 790 892 990
92 193 289 389 491 589 691 791 893 991
93 194 290 390 492 590 692 792 894 992
94 195 291 391 493 591 693 793 895 993
95 196 292 392 494 592 694 794 896 994
96 197 293 393 495 593 695 795 897 995
97 198 294 394 496 594 696 796 898 996
199 295 395 497 595 697 797 899 997
296 396 498 596 698 798
297 397 499 597 699 799
298 398
299 399
598
599
998
999

提示

【样例 1 解释】 这是第一组数据的样例说明。 所有水果一开始的情况是 1 1 0 0 1 1 1 0 1 1 0 0，一共有 6 个块。 在第一次挑水果组成果篮的过程中，编号为 1 3 5 8 9 11 的水果被挑了出来。 之后剩下的水果是 1 0 1 1 1 0，一共 4 个块。 在第二次挑水果组成果篮的过程中，编号为 2 4 6 12 的水果被挑了出来。 之后剩下的水果是 1 1，只有 1 个块。 在第三次挑水果组成果篮的过程中，编号为 7 的水果被挑了出来。 最后剩下的水果是 1，只有 1 个块。 在第四次挑水果组成果篮的过程中，编号为 10 的水果被挑了出来。

【数据范围】 对于 10% 的数据，n ≤ 5。 对于 30% 的数据，n ≤ 1000。 对于 70% 的数据，n ≤ 50000。 对于 100% 的数据，n ≤ 2 × 10^5

【提示】 由于数据规模较大，建议 C/C++ 选手使用 scanf 和 printf 语句输入、输出。

时间限制 1 秒
内存限制 512 MB
讨论 统计
上一题 下一题