QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#325605#7956. Walk Swappingmateberishvili#WA 121ms3852kbC++234.2kb2024-02-11 17:47:452024-02-11 17:47:45

Judging History

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

  • [2024-02-11 17:47:45]
  • 评测
  • 测评结果:WA
  • 用时:121ms
  • 内存:3852kb
  • [2024-02-11 17:47:45]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = (int) 3e3 + 5;
const int MOD = (int) 1e9 + 7;
const int P = 3491;

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

int mul(int a, int b, int m = MOD) {
	return a * 1ll * b % m;
}

int bpow(int a, int b, int m = MOD) {
	int res = 1;
	
	for (; b; b /= 2) {
		if (b & 1) {
			res = mul(res, a, m);
		}
		a = mul(a, a, m);
	}
	
	return res;
}

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

int 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;
}

int pref[MAXN];

int calc_fast(vector<int> A, vector<int> B) {
	if (A == B) {
		return 0;
	}
	
	vector<pair<int, int>> M;
	
	for (int i = 0; i < n; i++) {
		vector<int> nB = B;
		rotate(nB.begin(), nB.begin() + i, nB.end());
		int 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++) {
			int suf_part = add(pref[n - 1], MOD - pref[len-1]);
			int hsh_A = add(mul(add(pref[len - 1], MOD - pref[0]), P_inv), mul(pref[0], pw[len - 1]));
			int hsh_B = add(mul(pref[len - 2], P), A[len - 1]);
			
			for (int h: {hsh_A, hsh_B}) {
				int rot = (n - l) % n;
				int 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: 3648kb

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: 3620kb

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: 3772kb

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: 3596kb

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: 3580kb

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: 3572kb

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: 3524kb

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: 3644kb

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: 3636kb

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: 3716kb

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: 1ms
memory: 3636kb

input:

4
4 3 2 1
1 3 2 4

output:

1

result:

ok single line: '1'

Test #12:

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

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: 3800kb

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: 3640kb

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: 3568kb

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: 3768kb

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: 3772kb

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: 3616kb

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: 1ms
memory: 3644kb

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: 3632kb

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: 3716kb

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: 3836kb

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: 3852kb

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: 3636kb

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: 3572kb

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: 3628kb

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: 0ms
memory: 3648kb

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: 3796kb

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: 3612kb

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: 3652kb

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: 3588kb

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: 1ms
memory: 3568kb

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: 3640kb

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: -100
Wrong Answer
time: 121ms
memory: 3680kb

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:

13946

result:

wrong answer 1st lines differ - expected: '243210', found: '13946'