QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#305232#7956. Walk SwappingmshcherbaWA 1ms3492kbC++201.6kb2024-01-14 22:54:092024-01-14 22:54:10

Judging History

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

  • [2024-01-14 22:54:10]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3492kb
  • [2024-01-14 22:54:09]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int INF = 1e9;

VI zFunction(const VI& s)
{
	int n = SZ(s);
	VI z(n);
	int l = 0, r = 0;
	FOR(i, 1, n)
	{
		z[i] = 0;
		if (i <= r)
			z[i] = min(r - i + 1, z[i - l]);
		while (i + z[i] < n && s[i + z[i]] == s[z[i]])
			z[i]++;
		if (i + z[i] - 1 > r)
		{
			r = i + z[i] - 1;
			l = i;
		}
	}
	return z;
}

int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0);
	cout << fixed << setprecision(15);
	int n;
	cin >> n;
	VI a(n), b(n);
	for (int& x : a)
		cin >> x;
	for (int& x : b)
		cin >> x;
	VI c;
	int ans = INF;
	FOR(i, 0, n)
	{
		c.clear();
		FOR(j, 0, n - 1)
			c.PB(a[(i + j) % n]);
		VI d1 = c, d2 = c;
		reverse(ALL(d2));
		d1.PB(0);
		d1.insert(d1.end(), ALL(b));
		d1.insert(d1.end(), ALL(b));
		VI br = b;
		reverse(ALL(br));
		d2.PB(0);
		d2.insert(d2.end(), ALL(br));
		d2.insert(d2.end(), ALL(br));
		VI z1 = zFunction(d1), z2 = zFunction(d2);
		FOR(j, 0, n)
		{
			int x = z2[2 * n - j];
			if (z1[n + j] + x >= n - 1 && b[(n + j - 1 - x) % n] == a[(i + n - 1) % n])
			{
				ans = min(ans, (n - 1 - j) % (n - 1) * (n - 1) + max(0, n - 1 - x));
			}
		}
		b.PB(b[0]);
		b.erase(b.begin());
	}
	cout << (ans == INF ? -1 : ans) << "\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

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

input:

4
1 2 3 4
4 2 1 3

output:

1

result:

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