QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#72353#5167. 魔术师zhoukangyang10 1575ms183868kbC++171.4kb2023-01-15 14:58:452023-01-15 14:59:35

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-15 14:59:35]
  • 评测
  • 测评结果:10
  • 用时:1575ms
  • 内存:183868kb
  • [2023-01-15 14:58:45]
  • 提交

answer

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i) 
#define R(i, j, k) for(int i = (j); i >= (k); --i) 
#define ll long long 
#define vi vector < int > 
#define ull unsigned long long 
#define sz(a) ((int) (a).size())
#define me(a, x) memset(a, x, sizeof(a)) 
using namespace std;
const int N = 1 << 22, M = N * 20;
queue < int > q;

int Ha[N], f[N][11], mp[N];
int n, m, x[N], p[N], u[N];
inline int Hash(int *f) {
	int ret = 0;
	R(i, n, 1) {
		ret *= i;
		L(j, 1, i - 1) {
			ret += f[j] > f[i];
		}
	}
	return ret + 1;
}

int main() {
//	freopen("a.in", "r", stdin);
	int totp;
	cin >> totp >> n >> m;
	if(n > 10) 
		assert(false);
	L(i, 1, n) cin >> x[i];
	int aim = Hash(x);
	L(i, 1, n) p[i] = i;
	do {
		int w = Hash(p);
		assert(w < N);
		L(i, 1, n) f[w][i] = p[i];
	} while(next_permutation(p + 1, p + n + 1));
	q.push(1);
	while(!q.empty()) {
		int t = q.front();
		q.pop();
		L(i, 1, n) u[i] = f[t][i];
		if(t == aim) break;
		L(i, 1, n - m + 1) {
			reverse(u + i, u + i + m);
			int qwq = Hash(u);
			if(!mp[qwq]) q.push(qwq), mp[qwq] = t;
			reverse(u + i, u + i + m);
		}
	}
	
	if(aim != 1 && !mp[aim]) {
		cout << -1 << '\n';
		return 0;
	}
	
	vector < int > vc; 
	for(int u = aim; u != 1; u = mp[u]) {
		L(j, 1, n) 
			if(f[mp[u]][j] != f[u][j]) {
				vc.emplace_back(j - 1);
				break;
			}
	}
	cout << sz(vc) << '\n';
	for(auto u : vc) 
		cout << u << '\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 2ms
memory: 11488kb

input:

1 1 1
1

output:

0

result:

ok Perfect :) Use 0 operations

Test #2:

score: 5
Accepted
time: 366ms
memory: 166428kb

input:

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

output:

0

result:

ok Perfect :) Use 0 operations

Test #3:

score: 5
Accepted
time: 394ms
memory: 166228kb

input:

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

output:

-1

result:

ok No solutions

Test #4:

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

input:

1 4 3
1 2 3 4

output:

0

result:

ok Perfect :) Use 0 operations

Test #5:

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

input:

1 5 3
5 2 1 4 3

output:

2
0
2

result:

ok Perfect :) Use 2 operations

Test #6:

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

input:

1 5 3
3 2 1 4 5

output:

1
0

result:

ok Perfect :) Use 1 operations

Test #7:

score: 5
Accepted
time: 2ms
memory: 11460kb

input:

1 5 3
5 2 3 4 1

output:

3
0
2
0

result:

ok Perfect :) Use 3 operations

Test #8:

score: 5
Accepted
time: 418ms
memory: 168328kb

input:

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

output:

15
1
3
5
7
0
2
4
6
3
5
4
0
2
1
0

result:

ok Perfect :) Use 15 operations

Test #9:

score: 5
Accepted
time: 4ms
memory: 11512kb

input:

1 5 5
5 4 3 2 1

output:

1
0

result:

ok Perfect :) Use 1 operations

Test #10:

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

input:

1 6 5
5 6 1 2 3 4

output:

2
1
0

result:

ok Perfect :) Use 2 operations

Test #11:

score: 5
Accepted
time: 2ms
memory: 11556kb

input:

1 6 5
3 2 1 4 5 6

output:

-1

result:

ok No solutions

Test #12:

score: 5
Accepted
time: 3ms
memory: 11516kb

input:

1 6 5
6 5 4 3 2 1

output:

-1

result:

ok No solutions

Test #13:

score: 5
Accepted
time: 0ms
memory: 11484kb

input:

1 7 5
3 2 7 6 1 4 5

output:

3
0
2
1

result:

ok Perfect :) Use 3 operations

Test #14:

score: 5
Accepted
time: 4ms
memory: 11484kb

input:

1 7 5
5 2 7 4 3 6 1

output:

-1

result:

ok No solutions

Test #15:

score: 5
Accepted
time: 408ms
memory: 168780kb

input:

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

output:

6
2
4
3
5
2
1

result:

ok Perfect :) Use 6 operations

Test #16:

score: 5
Accepted
time: 421ms
memory: 167068kb

input:

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

output:

-1

result:

ok No solutions

Test #17:

score: 5
Accepted
time: 39ms
memory: 28056kb

input:

1 9 7
7 8 5 6 9 4 1 2 3

output:

9
0
1
2
0
2
1
0
1
0

result:

ok Perfect :) Use 9 operations

Test #18:

score: 5
Accepted
time: 33ms
memory: 25852kb

input:

1 9 7
1 6 9 8 3 2 5 4 7

output:

-1

result:

ok No solutions

Test #19:

score: 5
Accepted
time: 411ms
memory: 169448kb

input:

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

output:

8
0
2
0
1
3
2
3
0

result:

ok Perfect :) Use 8 operations

Test #20:

score: 5
Accepted
time: 432ms
memory: 167148kb

input:

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

output:

2
0
1

result:

ok Perfect :) Use 2 operations

Subtask #2:

score: 5
Accepted

Test #21:

score: 5
Accepted
time: 4ms
memory: 11484kb

input:

2 2 2
2 1

output:

1
0

result:

ok Perfect :) Use 1 operations

Test #22:

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

input:

2 3 2
1 3 2

output:

1
1

result:

ok Perfect :) Use 1 operations

Test #23:

score: 5
Accepted
time: 578ms
memory: 174452kb

input:

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

output:

15
1
2
3
4
5
6
7
5
6
3
4
5
3
4
0

result:

ok Perfect :) Use 15 operations

Test #24:

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

input:

2 4 4
1 2 3 4

output:

0

result:

ok Perfect :) Use 0 operations

Test #25:

score: 5
Accepted
time: 0ms
memory: 11464kb

input:

2 5 4
1 5 4 3 2

output:

1
1

result:

ok Perfect :) Use 1 operations

Test #26:

score: 5
Accepted
time: 0ms
memory: 11560kb

input:

2 4 4
3 4 1 2

output:

-1

result:

ok No solutions

Test #27:

score: 5
Accepted
time: 0ms
memory: 11460kb

input:

2 5 4
4 5 2 3 1

output:

-1

result:

ok No solutions

Test #28:

score: 5
Accepted
time: 1107ms
memory: 183036kb

input:

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

output:

10
2
4
6
1
3
0
2
1
2
0

result:

ok Perfect :) Use 10 operations

Test #29:

score: 5
Accepted
time: 1575ms
memory: 180896kb

input:

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

output:

-1

result:

ok No solutions

Test #30:

score: 5
Accepted
time: 1395ms
memory: 183868kb

input:

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

output:

11
2
1
2
3
0
1
4
2
1
0
4

result:

ok Perfect :) Use 11 operations

Test #31:

score: 5
Accepted
time: 995ms
memory: 179532kb

input:

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

output:

30
0
2
1
2
0
2
1
0
1
0
1
2
0
1
0
2
1
0
1
0
1
0
1
0
2
0
1
0
2
0

result:

ok Perfect :) Use 30 operations

Test #32:

score: 5
Accepted
time: 657ms
memory: 179304kb

input:

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

output:

24
1
0
1
2
1
0
2
0
1
0
2
1
2
1
0
1
0
1
2
1
2
0
2
1

result:

ok Perfect :) Use 24 operations

Test #33:

score: 5
Accepted
time: 1102ms
memory: 180924kb

input:

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

output:

-1

result:

ok No solutions

Test #34:

score: 5
Accepted
time: 390ms
memory: 166512kb

input:

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

output:

1
0

result:

ok Perfect :) Use 1 operations

Test #35:

score: 5
Accepted
time: 399ms
memory: 166608kb

input:

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

output:

-1

result:

ok No solutions

Subtask #3:

score: 0
Dangerous Syscalls

Test #36:

score: 0
Dangerous Syscalls

input:

3 30 29
19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 30 29 28 27 26 25 24 23 22 21 20

output:


result:


Subtask #4:

score: 0
Dangerous Syscalls

Test #56:

score: 0
Dangerous Syscalls

input:

4 30 30
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

output:


result:


Subtask #5:

score: 0
Dangerous Syscalls

Test #71:

score: 0
Dangerous Syscalls

input:

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

output:


result:


Subtask #6:

score: 0
Dangerous Syscalls

Test #101:

score: 0
Dangerous Syscalls

input:

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

output:


result:


Subtask #7:

score: 0
Dangerous Syscalls

Test #116:

score: 0
Dangerous Syscalls

input:

7 200 199
147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 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...

output:


result:


Subtask #8:

score: 0
Dangerous Syscalls

Test #141:

score: 0
Dangerous Syscalls

input:

8 200 200
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...

output:


result:


Subtask #9:

score: 0
Dangerous Syscalls

Test #156:

score: 0
Dangerous Syscalls

input:

9 1000 5
211 100 879 298 625 856 443 312 159 430 391 546 577 436 137 720 561 290 847 592 187 120 953 60 979 94 583 700 623 80 627 732 675 24 987 340 221 974 1 816 881 280 495 432 853 212 117 986 667 148 127 664 481 524 725 82 543 906 819 394 581 950 91 866 573 496 251 392 775 730 273 784 511 90 359 ...

output:


result:


Subtask #10:

score: 0
Dangerous Syscalls

Test #168:

score: 0
Dangerous Syscalls

input:

10 1000 4
758 267 63 485 736 202 48 317 86 106 157 637 213 476 900 811 830 915 333 457 665 423 51 881 837 615 228 201 151 69 87 753 312 999 810 483 409 630 790 497 120 838 969 170 3 271 316 365 831 598 801 199 931 200 768 16 357 874 869 481 771 262 508 850 146 67 136 674 670 649 845 621 109 602 150 ...

output:


result:


Subtask #11:

score: 0
Dangerous Syscalls

Test #176:

score: 0
Dangerous Syscalls

input:

11 1000 7
975 294 573 546 575 370 471 988 77 438 155 162 877 176 441 260 189 178 381 936 495 106 405 854 739 674 395 332 627 628 605 1000 1 422 485 594 879 882 849 620 265 424 55 500 149 378 47 708 137 410 775 44 283 112 823 70 499 64 397 606 793 190 753 752 545 580 651 206 963 730 815 968 263 698 6...

output:


result:


Subtask #12:

score: 0
Dangerous Syscalls

Test #187:

score: 0
Dangerous Syscalls

input:

12 1000 6
416 514 385 469 20 211 283 558 116 425 351 927 713 189 649 827 54 441 327 759 273 466 971 829 108 738 200 21 557 577 266 541 507 115 480 646 673 179 820 430 84 458 249 869 676 127 482 80 606 545 639 919 974 826 718 783 741 775 549 693 202 477 291 528 48 366 137 483 95 350 709 966 55 312 62...

output:


result:


Subtask #13:

score: 0
Dangerous Syscalls

Test #201:

score: 0
Dangerous Syscalls

input:

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

output:


result:


Subtask #14:

score: 0
Dangerous Syscalls

Test #231:

score: 0
Dangerous Syscalls

input:

14 60 60
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

output:


result:


Subtask #15:

score: 0
Dangerous Syscalls

Test #246:

score: 0
Dangerous Syscalls

input:

15 1000 999
419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 ...

output:


result:


Subtask #16:

score: 0
Dangerous Syscalls

Test #281:

score: 0
Dangerous Syscalls

input:

16 1000 1000
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...

output:


result: