QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#325609#7956. Walk Swappingmateberishvili#TL 136ms3860kbC++234.2kb2024-02-11 17:51:542024-02-11 17:51:54

Judging History

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

  • [2024-02-11 17:51:54]
  • 评测
  • 测评结果:TL
  • 用时:136ms
  • 内存:3860kb
  • [2024-02-11 17:51:54]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int MAXN = (int) 3e3 + 5;
const ll MOD = 494406068045569;
const int P = 3491;

ll add(ll a, ll b, ll m = MOD) {
	return a + b < m ? a + b : a + b - m;
}

ll mul(ll a, ll b, ll M = MOD) {
	ll ret = a * b - M * ull(1.L / M * a * b);
	return ret + M * (ret < 0) - M * (ret >= (ll)M);
}

ll bpow(ll b, ll e, ll mod = MOD) {
	ll ans = 1;
	for (; e; b = mul(b, b, mod), e /= 2)
		if (e & 1) ans = mul(ans, b, mod);
	return ans;
}

const ll P_inv = bpow(P, MOD - 2);

ll pw[MAXN];
int n;

void pre() {
	pw[0] = 1;
	
	for (int i = 1; i < MAXN; i++) {
		pw[i] = mul(pw[i - 1], P);
	}
}

map<vector<int>, int> gen(vector<int> A) {
	queue<pair<vector<int>, int>> Q;
	set<pair<vector<int>, int>> S;
	map<pair<vector<int>, int>, int> D;
	map<vector<int>, int> ans;
	
	for (int st = 0; st < n; st++) {
		Q.push({A, st});
		S.insert({A, st});
		D[{A, st}] = 0;
	}
	
	ans[A] = 0;
	
	while (!Q.empty()) {
		vector<int> v = Q.front().first;
		int pos = Q.front().second;
		Q.pop();
		
		if (!ans[v]) {
			ans[v] = D[{v, pos}];
		}
		
		for (int d: {-1, +1}) {
			int new_pos = (pos + d + n) % n;
			vector<int> new_v = v;
			swap(new_v[pos], new_v[new_pos]);
			if (!S.count({new_v, new_pos})) {
				D[{new_v, new_pos}] = D[{v, pos}] + 1;
				S.insert({new_v, new_pos});
				Q.push({new_v, new_pos});
			}
		}
	}
	
	return ans;
}

ll pref[MAXN];

int calc_fast(vector<int> A, vector<int> B) {
	if (A == B) {
		return 0;
	}
	
	vector<pair<ll, int>> M;
	
	for (int i = 0; i < n; i++) {
		vector<int> nB = B;
		rotate(nB.begin(), nB.begin() + i, nB.end());
		ll hsh = 0;
		
		for (int j = 0; j < n; j++) {
			hsh = add(hsh, mul(nB[j], pw[j]));
		}
		
		M.push_back({hsh, (n - i) % n});
	}
	
	sort(M.begin(), M.end());
	vector<int> st_block(M.size()), en_block(M.size());
	
	for (int i = 0; i < M.size(); i++) {
		if (i == 0 || M[i].first != M[i - 1].first) {
			st_block[i] = i;
		}
		else {
			st_block[i] = st_block[i - 1];
		}
	}
	
	for (int i = M.size() - 1; i >= 0; i--) {
		if (i == M.size() - 1 || M[i].first != M[i + 1].first) {
			en_block[i] = i;
		}
		else {
			en_block[i] = en_block[i + 1];
		}
	}
	
	int ans = (int) 1e9;
	
	for (int l = 0; l < n; l++) {
		for (int i = 0; i < n; i++) {
			pref[i] = add(mul(pw[i], A[i]), i > 0 ? pref[i - 1] : 0);
		}
		
		for (int len = 2; len <= n; len++) {
			ll suf_part = add(pref[n - 1], MOD - pref[len-1]);
			ll hsh_A = add(mul(add(pref[len - 1], MOD - pref[0]), P_inv), mul(pref[0], pw[len - 1]));
			ll hsh_B = add(mul(pref[len - 2], P), A[len - 1]);
			
			for (ll h: {hsh_A, hsh_B}) {
				int rot = (n - l) % n;
				ll hsh = add(h, suf_part);				
				int pos = lower_bound(M.begin(), M.end(), make_pair(hsh, rot)) - M.begin();
				
				if (pos < M.size() && M[pos].first == hsh) {
					for (int t: {pos, st_block[pos], en_block[pos]}) {
						int cur = len - 1;
						int pp = M[t].second;
						cur += min(abs(pp - rot), n - abs(pp - rot)) * (n - 1);                             
						ans = min(ans, cur);
					}
				}
				
				if (pos > 0 && M[pos - 1].first == hsh) {
					for (int t: {pos-1, st_block[pos-1], en_block[pos-1]}) {
						int cur = len - 1;
						int pp = M[t].second;
						cur += min(abs(pp - rot), n - abs(pp - rot)) * (n - 1);                             
						ans = min(ans, cur);
					}
				}
			}
		}
		
		rotate(A.begin(), A.begin() + 1, A.end());
	}
	
	return ans == 1e9 ? -1 : ans;
}

int main() {
	pre();
	
	cin >> n;
	vector<int> A(n), B(n);
	
	for (int i = 0; i < n; i++) {
		cin >> A[i];
	}
	
	for (int i = 0; i < n; i++) {
		cin >> B[i];
	}
	
	cout << calc_fast(A, B) << '\n';
	
//	map<vector<int>, int> D = gen(A);
//	
//	vector<int> P(n);
//	iota(P.begin(), P.end(), 1);
//	
//	do {
//		auto it = D.find(P);
//		int ans_slow = (it == D.end() ? -1 : it -> second);
//		int ans_fast = calc_fast(A, P);
//		
//		if (ans_slow != ans_fast) {
//			for (int i = 0; i < n; i++) {
//				cout << P[i] << ' ';
//			}
//			cout << endl;
//			cout << ans_slow << ' ' << ans_fast << endl;
//			exit(0);
//		}
//	}
//	while (next_permutation(P.begin(), P.end()));
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3772kb

input:

4
4 3 2 1
3 4 2 1

output:

1

result:

ok single line: '1'

Test #2:

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

input:

6
2 1 1 2 2 1
1 2 2 2 1 1

output:

7

result:

ok single line: '7'

Test #3:

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

input:

6
4 1 3 6 2 5
6 2 1 3 4 5

output:

-1

result:

ok single line: '-1'

Test #4:

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

input:

4
1 2 3 4
4 2 1 3

output:

2

result:

ok single line: '2'

Test #5:

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

input:

6
4 1 3 6 2 5
6 2 5 3 4 1

output:

13

result:

ok single line: '13'

Test #6:

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

input:

6
4 1 3 3 2 5
3 2 5 3 4 1

output:

12

result:

ok single line: '12'

Test #7:

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

input:

4
4 3 2 1
1 3 2 4

output:

1

result:

ok single line: '1'

Test #8:

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

input:

5
4 3 5 2 1
1 3 5 4 2

output:

2

result:

ok single line: '2'

Test #9:

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

input:

5
4 3 5 2 1
1 4 3 5 2

output:

4

result:

ok single line: '4'

Test #10:

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

input:

5
1 1 1 2 1
2 1 1 1 1

output:

2

result:

ok single line: '2'

Test #11:

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

input:

4
4 3 2 1
1 3 2 4

output:

1

result:

ok single line: '1'

Test #12:

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

input:

4
4 3 2 1
1 3 4 2

output:

2

result:

ok single line: '2'

Test #13:

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

input:

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

output:

-1

result:

ok single line: '-1'

Test #14:

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

input:

5
1 4 5 3 2
5 3 2 1 4

output:

8

result:

ok single line: '8'

Test #15:

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

input:

5
1 2 3 4 5
5 2 1 3 4

output:

3

result:

ok single line: '3'

Test #16:

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

input:

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

output:

-1

result:

ok single line: '-1'

Test #17:

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

input:

10
1 2 3 2 2 2 1 1 1 1
2 1 1 1 1 1 2 2 3 2

output:

41

result:

ok single line: '41'

Test #18:

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

input:

10
1 1 1 2 2 4 4 4 2 2
1 1 2 2 4 4 2 2 1 4

output:

12

result:

ok single line: '12'

Test #19:

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

input:

12
3 3 3 2 2 2 4 4 2 2 1 3
3 3 2 2 4 4 2 2 2 1 3 3

output:

13

result:

ok single line: '13'

Test #20:

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

input:

12
3 3 2 2 2 2 4 4 2 2 1 2
2 2 2 2 4 4 2 2 2 1 3 3

output:

19

result:

ok single line: '19'

Test #21:

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

input:

12
3 3 2 4 2 2 4 4 2 2 1 2
2 2 2 2 4 4 2 2 4 1 3 3

output:

-1

result:

ok single line: '-1'

Test #22:

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

input:

20
3 4 4 5 1 2 3 2 5 1 1 5 3 2 4 5 1 2 3 5
2 3 5 4 4 5 1 2 3 2 5 3 1 1 5 3 2 4 5 1

output:

49

result:

ok single line: '49'

Test #23:

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

input:

20
3 4 4 5 1 2 3 2 5 1 1 5 3 2 4 5 1 2 3 5
3 2 3 4 5 1 2 3 5 4 4 5 1 2 3 2 5 1 1 5

output:

158

result:

ok single line: '158'

Test #24:

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

input:

100
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 100
99 1...

output:

109

result:

ok single line: '109'

Test #25:

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

input:

100
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 100
100 ...

output:

89

result:

ok single line: '89'

Test #26:

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

input:

100
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 100
51 5...

output:

4924

result:

ok single line: '4924'

Test #27:

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

input:

100
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 100
51 5...

output:

4905

result:

ok single line: '4905'

Test #28:

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

input:

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

output:

3990

result:

ok single line: '3990'

Test #29:

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

input:

100
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1
3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 ...

output:

125

result:

ok single line: '125'

Test #30:

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

input:

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

output:

-1

result:

ok single line: '-1'

Test #31:

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

input:

100
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1
2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 ...

output:

79

result:

ok single line: '79'

Test #32:

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

input:

100
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1
2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 ...

output:

-1

result:

ok single line: '-1'

Test #33:

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

input:

100
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 ...

output:

0

result:

ok single line: '0'

Test #34:

score: 0
Accepted
time: 136ms
memory: 3632kb

input:

1000
458 51 4 190 103 444 401 456 34 970 169 517 283 66 571 282 233 161 32 376 168 616 993 347 213 597 334 652 471 532 552 987 353 613 665 305 477 632 331 293 939 598 175 813 10 890 423 560 502 857 277 18 283 461 6 231 233 648 929 75 896 807 900 2 582 84 81 107 255 145 909 562 492 58 218 575 7 610 6...

output:

243210

result:

ok single line: '243210'

Test #35:

score: 0
Accepted
time: 135ms
memory: 3860kb

input:

1000
323 302 194 991 814 729 763 611 294 128 752 772 136 693 300 575 118 965 888 999 288 837 534 470 436 195 8 958 448 216 697 295 53 341 577 460 543 724 79 593 490 800 218 336 7 448 401 716 7 920 740 21 87 208 202 422 812 528 196 475 633 732 170 423 975 901 412 117 829 457 420 941 664 644 858 473 9...

output:

243013

result:

ok single line: '243013'

Test #36:

score: -100
Time Limit Exceeded

input:

3000
2057 2074 2349 1090 597 671 2074 92 892 304 1749 2393 935 2200 2859 293 2392 127 1960 1991 1842 2447 1783 1669 599 1936 887 1490 296 478 2334 250 864 1697 1833 325 1801 2950 2704 51 1868 2860 820 1495 1123 1 2122 2135 1826 294 612 1771 2181 160 1358 587 931 409 934 2622 516 2199 399 1008 1446 3...

output:


result: