QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#296215#7956. Walk Swappingdefyers#WA 1ms3616kbC++172.2kb2024-01-02 14:38:032024-01-02 14:38:04

Judging History

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

  • [2024-01-02 14:38:04]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3616kb
  • [2024-01-02 14:38:03]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

using ll = long long;
using pii = pair<int, int>;

using ull = unsigned long long;
const ull X = 2748283;

void solve(int TC) {
	int n;
	cin >> n;
	
	ll ans = 1e9;

	vector<ull> a(n), b(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> b[i];
	}

	vector<ull> pwr(n + 1);
	pwr[0] = 1; 
	for (int i = 1; i < n; i++) {
		pwr[i] = pwr[i - 1] * X;
	}

	unordered_map<ull, int> rotate;
	rotate.reserve(8192);
	{
		ull H = 0;
		for (int i = 0; i < n; i++) {
			H = H * X + b[i];
		}
		// cout << "@ " << H << endl;
		rotate[H] = 0;
		for (int i = 0; i < n; i++) {
			H = (H - pwr[n - 1] * b[i]) * X + b[i];
			rotate[H] = min(i + 1, n - (i + 1));
		}
	}

	ull oH = 0;
	for (int i = 0; i < n; i++) {
		oH = oH * X + a[i];
	}

	if (rotate.count(oH)) {
		ans = min(ans, rotate[oH] * ll(n - 1));
	}


	for (int i = 0; i < n; i++) {
		ull H = oH;
		vector<ull> A = a;
		// cout << "!" << oH << endl;
		for (int j = 1; j <= n; j++) {
			int x = (i + j) % n;
			int p = (i + j - 1) % n;
			H -= A[p] * pwr[n - 1 - p];
			H -= A[x] * pwr[n - 1 - x];
			swap(A[p], A[x]);
			H += A[p] * pwr[n - 1 - p];
			H += A[x] * pwr[n - 1 - x];

			// cout << "forward: ";
			// for (int j = 0; j < n; j++) {
			// 	cout << A[j] << " ";
			// }
			// cout << " hash: " << H;
			// cout << endl;

			if (rotate.count(H)) {
				ans = min(ans, j + rotate[H] * ll(n - 1));
			}
		}
		H = oH;
		A = a;
		for (int j = 1; j <= n; j++) {
			int x = (i - j + n) % n;
			int p = (i - j + n + 1) % n;
			H -= A[p] * pwr[n - 1 - p];
			H += A[x] * pwr[n - 1 - x];
			swap(A[p], A[x]);

			// cout << "backward: ";
			// for (int j = 0; j < n; j++) {
			// 	cout << A[j] << " ";
			// }
			// cout << endl;

			if (rotate.count(H)) {
				ans = min(ans, j + rotate[H] * ll(n - 1));
			}
		}
	}


	if (ans == 1e9) {
		cout << -1 << "\n";
	}
	else {
		cout << ans << "\n";
	}
}

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	cout << fixed << setprecision(10);

	int t = 1;
	// cin >> t;

	for (int i = 1; i <= t; i++) {
		solve(i);
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
4 3 2 1
3 4 2 1

output:

1

result:

ok single line: '1'

Test #2:

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

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

input:

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

output:

-1

result:

ok single line: '-1'

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 3508kb

input:

4
1 2 3 4
4 2 1 3

output:

4

result:

wrong answer 1st lines differ - expected: '2', found: '4'