QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#263789#7868. 天空度假山庄yyyyxh100 ✓63ms155964kbC++231.9kb2023-11-25 07:30:372023-11-25 07:30:39

Judging History

你现在查看的是最新测评结果

  • [2023-11-25 07:30:39]
  • 评测
  • 测评结果:100
  • 用时:63ms
  • 内存:155964kb
  • [2023-11-25 07:30:37]
  • 提交

answer

#include <cstdio>
#include <cassert>
#include <bitset>
#include <vector>
using namespace std;
int read(){
	char c=getchar();int x=0;
	while(c<48||c>57) c=getchar();
	do x=(x<<1)+(x<<3)+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
const int N=1000003,M=223,T=1000003;
const int L=220;
int n,k,m,nn;
bitset<24315> f[M][M];
int seq[T],rk;
void cons(int x,int k,int cur){
	if(!x||!k) return;
	if(cur>=x&&f[x-1][k-1][cur-x]){
		seq[++rk]=x;
		cons(x-1,k-1,cur-x);
		return;
	}
	if(f[x-1][k][cur]){
		cons(x-1,k,cur);
		return;
	}
}
void solve(){
	for(int i=0;i<n;++i){
		int tmp=i;
		for(int j=0;j<k;++j){
			if(!i&&!j) continue;
			if(i==n-1&&j) continue;
			if(j){
				tmp+=seq[j];
				if(tmp>=n) tmp-=n;
			}
			printf("%d ",tmp+1);
		}
	}
	putchar('\n');
}
bitset<24315> g[M];
int main(){
	n=read();k=read();
	if(k==1){
		for(int i=2;i<=n;++i) printf("%d ",i);
		putchar('\n');
		return 0;
	}
	if(k==2){
		printf("2 3 4 2 ");
		for(int i=4;i<n;++i) printf("%d %d ",i+1,i);
		printf("1 %d \n",n);
		return 0;
	}
	f[0][0].set(0);
	for(int i=1;i<=L;++i){
		f[i][0]=f[i-1][0];
		for(int j=1;j<=i;++j) f[i][j]=f[i-1][j]|(f[i-1][j-1]<<i);
	}
	int pp=(n-1)>>1;
	if(k<=L){
		int ss=min(L,pp);
		for(int i=f[ss][k]._Find_first();i!=int(f[ss][k].size());i=f[ss][k]._Find_next(i))
			if(i%n==1){
				cons(ss,k,i);
				solve();
				return 0;
			}
	}
	for(int t=0;t<=L;++t)
		for(int i=f[L][t]._Find_first();i!=int(f[L][t].size());i=f[L][t]._Find_next(i)) g[t].set(i%n);
	int tmp=1,cnt=0;
	for(int i=pp;i>L&&cnt<k;--i){
		tmp-=i;++cnt;seq[++rk]=i;
		if(tmp<0) tmp+=n;
		if(k-cnt<=L&&g[k-cnt][tmp]){
			int t=k-cnt;
			for(int j=f[L][t]._Find_first();j!=int(f[L][t].size());j=f[L][t]._Find_next(j))
				if(j%n==tmp){
					cons(L,t,j);
					solve();
					return 0;
				}
			assert(0);
		}
	}
	assert(0);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 1ms
memory: 3732kb

input:

8216 1

output:

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 100 101 102 10...

result:

ok correct

Test #2:

score: 0
Accepted
time: 1ms
memory: 3748kb

input:

5166 2

output:

2 3 4 2 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 52 51 53 52 54 53 55 ...

result:

ok correct

Test #3:

score: 0
Accepted
time: 1ms
memory: 3804kb

input:

7445 2

output:

2 3 4 2 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 52 51 53 52 54 53 55 ...

result:

ok correct

Test #4:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

1295 2

output:

2 3 4 2 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 52 51 53 52 54 53 55 ...

result:

ok correct

Subtask #2:

score: 20
Accepted

Test #5:

score: 20
Accepted
time: 48ms
memory: 151936kb

input:

86132 9

output:

43066 86130 43061 86123 43052 86112 86131 1 2 43067 86131 43062 86124 43053 86113 86132 2 3 43068 86132 43063 86125 43054 86114 1 3 4 43069 1 43064 86126 43055 86115 2 4 5 43070 2 43065 86127 43056 86116 3 5 6 43071 3 43066 86128 43057 86117 4 6 7 43072 4 43067 86129 43058 86118 5 7 8 43073 5 43068 ...

result:

ok correct

Test #6:

score: 0
Accepted
time: 54ms
memory: 153768kb

input:

73452 11

output:

36726 73450 36721 73443 36712 73432 73444 73448 73451 1 2 36727 73451 36722 73444 36713 73433 73445 73449 73452 2 3 36728 73452 36723 73445 36714 73434 73446 73450 1 3 4 36729 1 36724 73446 36715 73435 73447 73451 2 4 5 36730 2 36725 73447 36716 73436 73448 73452 3 5 6 36731 3 36726 73448 36717 7343...

result:

ok correct

Test #7:

score: 0
Accepted
time: 34ms
memory: 153340kb

input:

23283 20

output:

11642 23282 11638 23276 11630 23266 11618 23252 11602 23234 11582 23212 23257 23264 23270 23275 23279 23282 1 2 11643 23283 11639 23277 11631 23267 11619 23253 11603 23235 11583 23213 23258 23265 23271 23276 23280 23283 2 3 11644 1 11640 23278 11632 23268 11620 23254 11604 23236 11584 23214 23259 23...

result:

ok correct

Test #8:

score: 0
Accepted
time: 42ms
memory: 153608kb

input:

36944 17

output:

18472 36942 18467 36935 18458 36924 18445 36909 18428 36890 36925 36931 36936 36940 36943 1 2 18473 36943 18468 36936 18459 36925 18446 36910 18429 36891 36926 36932 36937 36941 36944 2 3 18474 36944 18469 36937 18460 36926 18447 36911 18430 36892 36927 36933 36938 36942 1 3 4 18475 1 18470 36938 18...

result:

ok correct

Test #9:

score: 0
Accepted
time: 40ms
memory: 155964kb

input:

61927 10

output:

30964 61926 30960 61920 30952 61910 61923 61926 1 2 30965 61927 30961 61921 30953 61911 61924 61927 2 3 30966 1 30962 61922 30954 61912 61925 1 3 4 30967 2 30963 61923 30955 61913 61926 2 4 5 30968 3 30964 61924 30956 61914 61927 3 5 6 30969 4 30965 61925 30957 61915 1 4 6 7 30970 5 30966 61926 3095...

result:

ok correct

Subtask #3:

score: 20
Accepted

Dependency #2:

100%
Accepted

Test #10:

score: 20
Accepted
time: 3ms
memory: 151416kb

input:

111 17

output:

56 104 8 22 35 47 58 68 77 85 92 98 103 107 110 1 2 57 105 9 23 36 48 59 69 78 86 93 99 104 108 111 2 3 58 106 10 24 37 49 60 70 79 87 94 100 105 109 1 3 4 59 107 11 25 38 50 61 71 80 88 95 101 106 110 2 4 5 60 108 12 26 39 51 62 72 81 89 96 102 107 111 3 5 6 61 109 13 27 40 52 63 73 82 90 97 103 10...

result:

ok correct

Test #11:

score: 0
Accepted
time: 7ms
memory: 151504kb

input:

462 86

output:

221 440 196 295 377 458 76 155 233 310 386 461 73 146 218 289 359 428 34 101 167 232 296 359 421 20 80 139 197 254 310 365 419 10 62 113 163 212 260 307 353 398 442 23 65 106 146 185 223 260 296 331 365 398 430 461 29 58 86 113 139 164 188 211 233 254 274 293 311 328 344 359 373 386 398 409 419 428 ...

result:

ok correct

Test #12:

score: 0
Accepted
time: 4ms
memory: 151268kb

input:

262 43

output:

131 189 230 8 47 85 122 158 193 227 260 30 61 91 120 148 175 201 226 250 11 33 54 74 93 111 128 144 159 173 186 198 209 219 228 236 243 249 254 258 261 1 2 132 190 231 9 48 86 123 159 194 228 261 31 62 92 121 149 176 202 227 251 12 34 55 75 94 112 129 145 160 174 187 199 210 220 229 237 244 250 255 ...

result:

ok correct

Test #13:

score: 0
Accepted
time: 23ms
memory: 151272kb

input:

672 125

output:

221 440 563 13 134 254 373 491 608 52 167 281 394 506 617 55 164 272 379 485 590 22 125 227 328 428 527 625 50 146 241 335 428 520 611 29 118 206 293 379 464 548 631 41 122 202 281 359 436 512 587 661 62 134 205 275 344 412 479 545 610 2 65 127 188 248 307 365 422 478 533 587 640 20 71 121 170 218 2...

result:

ok correct

Test #14:

score: 0
Accepted
time: 3ms
memory: 151464kb

input:

747 127

output:

218 344 469 593 716 91 212 332 451 569 686 55 170 284 397 509 620 730 92 200 307 413 518 622 725 80 181 281 380 478 575 671 19 113 206 298 389 479 568 656 743 82 167 251 334 416 497 577 656 734 64 140 215 289 362 434 505 575 644 712 32 98 163 227 290 352 413 473 532 590 647 703 11 65 118 170 221 271...

result:

ok correct

Test #15:

score: 0
Accepted
time: 11ms
memory: 153312kb

input:

404 72

output:

202 345 11 80 148 215 281 346 6 69 131 192 252 311 369 22 78 133 187 240 292 343 393 38 86 133 179 224 268 311 353 394 30 69 107 144 180 215 249 282 314 345 375 404 28 55 81 106 130 153 175 196 216 235 253 270 286 301 315 328 340 351 361 370 378 385 391 396 400 403 1 2 203 346 12 81 149 216 282 347 ...

result:

ok correct

Subtask #4:

score: 20
Accepted

Test #16:

score: 20
Accepted
time: 35ms
memory: 151920kb

input:

1777 229

output:

889 1776 885 1770 877 1760 865 1746 849 1728 829 1049 1268 1486 1703 142 357 571 784 996 1207 1417 1626 57 264 470 675 879 1082 1284 1485 1685 107 305 502 698 893 1087 1280 1472 1663 76 265 453 640 826 1011 1195 1378 1560 1741 144 323 501 678 854 1029 1203 1376 1548 1719 112 281 449 616 782 947 1111...

result:

ok correct

Test #17:

score: 0
Accepted
time: 28ms
memory: 153836kb

input:

1129 229

output:

565 1128 561 1122 553 1112 541 1098 525 1080 505 1058 149 368 586 803 1019 105 319 532 744 955 36 245 453 660 866 1071 146 349 551 752 952 22 220 417 613 808 1002 66 258 449 639 828 1016 74 260 445 629 812 994 46 226 405 583 757 930 1102 144 314 483 651 818 984 20 184 347 509 670 830 989 18 175 331 ...

result:

ok correct

Test #18:

score: 0
Accepted
time: 63ms
memory: 153612kb

input:

4253 233

output:

2127 4252 2123 4246 2115 4236 2103 4222 2087 4204 2067 4182 2043 4156 2015 4126 1983 2203 2422 2640 2857 3073 3288 3502 3715 3927 4138 95 304 512 719 925 1130 1334 1537 1739 1940 2140 2339 2537 2734 2930 3122 3312 3501 3689 3876 4062 4247 178 361 543 724 904 1083 1261 1438 1614 1789 1963 2136 2308 2...

result:

ok correct

Test #19:

score: 0
Accepted
time: 50ms
memory: 152476kb

input:

2311 233

output:

1156 2310 1152 2304 1144 2294 1132 2280 1116 2262 1096 2240 1072 2214 1044 2184 1012 2150 59 278 496 713 929 1144 1358 1571 1783 1994 2202 95 298 500 701 901 1100 1298 1495 1691 1886 2080 2273 154 345 535 724 912 1099 1285 1470 1654 1837 2019 2200 69 248 426 603 779 954 1128 1301 1473 1644 1814 1983...

result:

ok correct

Test #20:

score: 0
Accepted
time: 39ms
memory: 153316kb

input:

6712 114

output:

221 386 498 609 719 828 936 1043 1149 1254 1358 1461 1563 1664 1764 1863 1961 2058 2154 2249 2343 2436 2528 2619 2709 2798 2886 2973 3059 3144 3228 3311 3393 3474 3554 3633 3711 3788 3864 3939 4013 4086 4158 4229 4299 4368 4436 4503 4569 4634 4698 4761 4823 4884 4944 5003 5061 5118 5174 5229 5283 53...

result:

ok correct

Test #21:

score: 0
Accepted
time: 16ms
memory: 151268kb

input:

1050 114

output:

221 440 658 875 41 256 470 631 737 842 946 1049 101 202 302 401 499 596 692 787 881 974 16 107 197 286 374 461 547 632 716 799 881 962 1042 71 149 226 302 377 451 524 596 667 737 806 874 941 1007 22 86 149 211 272 332 391 449 506 562 617 671 724 776 827 877 926 974 1021 17 62 106 149 191 232 272 311...

result:

ok correct

Test #22:

score: 0
Accepted
time: 48ms
memory: 152400kb

input:

1132 514

output:

566 1130 561 1123 552 1112 539 1097 522 1078 501 1055 476 1028 447 997 414 962 377 923 336 880 291 833 242 782 189 727 132 668 71 605 6 538 1069 467 996 392 919 313 838 230 753 143 664 52 571 1089 474 990 373 887 268 780 159 669 46 554 1061 435 940 312 815 185 686 54 553 1051 416 912 275 769 130 622...

result:

ok correct

Test #23:

score: 0
Accepted
time: 48ms
memory: 152012kb

input:

1130 514

output:

565 1128 560 1121 551 1110 538 1095 521 1076 500 1053 475 1026 446 995 413 960 376 921 335 878 290 831 241 780 188 725 131 666 70 603 5 536 1066 465 993 390 916 311 835 228 750 141 661 50 568 1085 471 986 370 883 265 776 156 665 43 550 1056 431 935 308 810 181 681 50 548 1045 411 906 270 763 125 616...

result:

ok correct

Subtask #5:

score: 35
Accepted

Dependency #1:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #24:

score: 35
Accepted
time: 46ms
memory: 151840kb

input:

1151 564

output:

576 1150 572 1144 564 1134 552 1120 536 1102 516 1080 492 1054 464 1024 432 990 396 952 356 910 312 864 264 814 212 760 156 702 96 640 32 574 1115 504 1043 430 967 352 887 270 803 184 715 94 623 1151 527 1053 427 951 323 845 215 735 103 621 1138 503 1018 381 894 255 766 125 634 1142 498 1004 358 862...

result:

ok correct

Test #25:

score: 0
Accepted
time: 31ms
memory: 155900kb

input:

1042 511

output:

521 1040 516 1033 507 1022 494 1007 477 988 456 965 431 938 402 907 369 872 332 833 291 790 246 743 197 692 144 637 87 578 26 515 1003 448 934 377 861 302 784 223 703 140 618 53 529 1004 436 909 339 810 238 707 133 600 24 489 953 374 836 255 715 132 590 5 461 916 328 781 191 642 50 499 947 352 798 2...

result:

ok correct

Test #26:

score: 0
Accepted
time: 52ms
memory: 152528kb

input:

1170 575

output:

585 1168 580 1161 571 1150 558 1135 541 1116 520 1093 495 1066 466 1035 433 1000 396 961 355 918 310 871 261 820 208 765 151 706 90 643 25 576 1126 505 1053 430 976 351 895 268 810 181 721 90 628 1165 531 1066 430 963 325 856 216 745 103 630 1156 511 1035 388 910 261 781 130 648 1165 511 1026 370 88...

result:

ok correct

Test #27:

score: 0
Accepted
time: 36ms
memory: 151916kb

input:

1249 615

output:

625 1248 621 1242 613 1232 601 1218 585 1200 565 1178 541 1152 513 1122 481 1088 445 1050 405 1008 361 962 313 912 261 858 205 800 145 738 81 672 13 602 1190 528 1114 450 1034 368 950 282 862 192 770 98 674 1249 574 1147 470 1041 362 931 250 817 134 699 14 577 1139 451 1011 321 879 187 743 49 603 11...

result:

ok correct

Test #28:

score: 0
Accepted
time: 20ms
memory: 151864kb

input:

746 364

output:

373 744 368 737 359 726 346 711 329 692 308 669 283 642 254 611 221 576 184 537 143 494 98 447 49 396 742 341 685 282 624 219 559 152 490 81 417 6 340 673 259 590 174 503 85 412 738 317 641 218 540 115 435 8 326 643 213 528 96 409 721 286 596 159 467 28 334 639 197 500 56 357 657 210 508 59 355 650 ...

result:

ok correct

Test #29:

score: 0
Accepted
time: 44ms
memory: 151912kb

input:

1146 565

output:

573 1144 568 1137 559 1126 546 1111 529 1092 508 1069 483 1042 454 1011 421 976 384 937 343 894 298 847 249 796 196 741 139 682 78 619 13 552 1090 481 1017 406 940 327 859 244 774 157 685 66 592 1117 495 1018 394 915 289 808 180 697 67 582 1096 463 975 340 850 213 721 82 588 1093 451 954 310 811 165...

result:

ok correct

Test #30:

score: 0
Accepted
time: 24ms
memory: 152532kb

input:

554 265

output:

277 552 272 545 263 534 250 519 233 500 212 477 187 450 158 419 125 384 88 345 47 302 2 255 507 204 454 149 397 90 336 27 271 514 202 443 129 368 52 289 525 206 440 119 351 28 258 478 143 361 24 240 455 115 328 540 197 407 62 270 477 129 334 538 187 389 36 236 435 79 276 472 113 307 500 138 329 519 ...

result:

ok correct

Test #31:

score: 0
Accepted
time: 46ms
memory: 152004kb

input:

1061 519

output:

531 1060 527 1054 519 1044 507 1030 491 1012 471 990 447 964 419 934 387 900 351 862 311 820 267 774 219 724 167 670 111 612 51 550 1048 484 980 414 908 340 832 262 752 180 668 94 580 4 488 971 392 873 292 771 188 665 80 555 1029 441 913 323 793 201 669 75 541 1006 409 872 273 734 133 592 1050 446 9...

result:

ok correct

Test #32:

score: 0
Accepted
time: 8ms
memory: 151736kb

input:

173 78

output:

87 172 83 166 69 142 41 112 9 78 146 40 106 171 62 125 14 75 135 21 79 136 19 74 128 8 60 111 161 37 85 132 5 50 94 137 6 47 87 126 164 28 64 99 133 166 25 56 86 115 143 170 23 48 72 95 117 138 158 4 22 39 55 70 84 97 109 120 130 139 147 154 160 165 169 172 1 2 88 173 84 167 70 143 42 113 10 79 147 ...

result:

ok correct

Test #33:

score: 0
Accepted
time: 41ms
memory: 153692kb

input:

884 430

output:

442 882 437 875 428 864 415 849 398 830 377 807 352 780 323 749 290 714 253 675 212 632 167 585 118 534 65 479 8 420 831 357 766 290 697 219 624 144 547 65 466 866 381 779 292 688 199 593 102 494 1 391 780 284 671 173 558 58 441 823 320 700 195 573 66 442 817 307 680 168 539 25 394 762 245 611 92 45...

result:

ok correct

Test #34:

score: 0
Accepted
time: 48ms
memory: 152472kb

input:

1089 537

output:

545 1088 541 1082 533 1072 521 1058 505 1040 485 1018 461 992 433 962 401 928 365 890 325 848 281 802 233 752 181 698 125 640 65 578 1 512 1022 442 950 368 874 290 794 208 710 122 622 32 530 1027 434 929 334 827 230 721 122 611 10 497 983 379 863 257 739 131 611 1 479 956 343 818 203 676 59 530 1000...

result:

ok correct

Test #35:

score: 0
Accepted
time: 16ms
memory: 151196kb

input:

433 207

output:

217 432 213 426 205 416 193 402 177 384 157 362 133 333 93 285 43 233 422 177 364 117 302 53 236 418 166 346 92 270 14 190 365 106 279 18 189 359 95 263 430 163 328 59 222 384 112 272 431 156 313 36 191 345 65 217 368 85 234 382 96 242 387 98 241 383 91 231 370 75 212 348 50 184 317 16 147 277 406 1...

result:

ok correct