QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#341676#7956. Walk Swappingucup-team2981#WA 1ms3776kbC++202.2kb2024-02-29 20:29:452024-02-29 20:29:46

Judging History

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

  • [2024-02-29 20:29:46]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3776kb
  • [2024-02-29 20:29:45]
  • 提交

answer

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;

void Hollwo_Pelw();

signed main(){
#ifndef hollwo_pelw_local
	if (fopen(".inp", "r"))
		assert(freopen(".inp", "r", stdin)), assert(freopen(".out", "w", stdout));
#else
	using namespace chrono;
	auto start = steady_clock::now();
#endif
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
	int testcases = 1;
	// cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
#ifdef hollwo_pelw_local
	auto end = steady_clock::now();
	cout << "\nExecution time : " << duration_cast<milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}

const int N = 3005;

int n, a[N], b[N], c[N], match[N], res = 2e9;


inline int get(int l, int r) {
	if (l <= r)
		return match[r] - (l ? match[l - 1] : 0);
	return get(l, n - 1) + get(0, r);
}

void solve() {
	for (int p = 0; p < 2; p++) {
		for (int i = 0; i < n; i++)
			c[i] = a[(i + p) % n];
		
		// cout << "P = " << p << '\n';
		// for (int i = 0; i < n; i++)
		// 	cout << c[i] << " \n"[i == n - 1];
		// for (int i = 0; i < n; i++)
		// 	cout << b[i] << " \n"[i == n - 1];
		

		int move = (n - 1) * p;

		vector<int> pos;
		for (int i = 0; i < n; i++) {
			if (b[i] != c[i])
				pos.push_back(i);
			match[i] = c[(i + 1) % n] == b[i] + (i == 0 ? 0 : match[i - 1]);
		}

		for (int i = 0; i < (int) pos.size(); i++) {
			int l = pos[(i + 1) % pos.size()], r = pos[i] % n; // check if path from l -> r can make b == c

			// cout << l << " -> " << r << '\n';

			int diff = (r - l + n) % n;
			// cout << get(l + r) + (c[l] == b[r]) << diff << '\n';

			if (get(l, (r + n - 1) % n) + (c[l] == b[r]) == diff + 1)
				res = min(res, diff + move);

		}

		if (pos.empty())
			res = min(res, move);
	}
}

void Hollwo_Pelw(){
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	} 
	for (int i = 0; i < n; i++) {
		cin >> b[i];
	}

	for (int turn = 2; turn --; ) {
		solve();
		reverse(a, a + n);
		reverse(b, b + n);
	}
	
	cout << (res == 2e9 ? -1 : res) << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3612kb

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

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

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

input:

4
1 2 3 4
4 2 1 3

output:

2

result:

ok single line: '2'

Test #5:

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

input:

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

output:

-1

result:

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