QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#303611 | #7956. Walk Swapping | PPP# | WA | 1ms | 5636kb | C++17 | 3.2kb | 2024-01-12 20:09:40 | 2024-01-12 20:09:41 |
Judging History
answer
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
typedef long double ld;
int n;
const int maxN = 6005;
int lcp[maxN][maxN];
int A[maxN], B[maxN];
vector<int> x, y;
int solve() {
for (int i = 0; i < n; i++) {
A[i] = A[i + n] = x[i];
B[i] = B[i + n] = y[i];
}
for (int i = 0; i < 2 * n; i++) {
for (int j = 0; j < 2 * n; j++) {
if (A[i] != B[j]) lcp[i][j] = 0;
else if (i > 0 && j > 0) lcp[i][j] = lcp[i - 1][j - 1] + 1;
else lcp[i][j] = 1;
}
}
int best = 1e9;
for (int p = 0; p < n; p++) {
//circles
for (int c = 0; c < n - 1; c++) {
int from_a = p + c;
from_a %= n;
from_a += n;
int from_b = p + n - 1;
from_b %= n;
from_b += n;
int X = min(lcp[from_a][from_b], c);
int len_c = X;
if (len_c == c) {
//it + n - 1
from_a = p + n - 1;
from_a %= n;
from_a += n;
from_b = p + n - 1 - c;
from_b %= n;
from_b += n;
int Y = min(lcp[from_a][from_b], n - 1 - c);
len_c += Y;
if (len_c == n - 1) {
if (A[p] == B[p]) {
len_c++;
}
}
}
if (len_c == n) {
best = min(best, c * n);
break;
}
int lft = n - len_c;
if (lft == 1) {
continue;
}
if (lft <= n - 1 - c + 1) {
if (B[p] != A[(p + c + 1) % n]) continue;
int from_a = (p + c + lft - 1) % n;
from_a += n;
int from_b = (p + lft - 2) % n;
from_b += n;
if (lcp[from_a][from_b] >= lft - 2 && A[p] == B[(p + lft - 1) % n]) {
best = min(best, c * n + lft);
break;
}
}
else {
if (A[p] != B[p + lft - 1]) continue;
if (B[p] != B[p + c + 1]) continue;
int D = lft - (n - c);
if (lcp[p + D][p + lft - 2] < D) continue;
if (lcp[p + n - 1][p + n - 2 - c] < n - 2 - c) continue;
best = min(best, c * n + lft);
break;
}
}
}
return best;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef DEBUG
freopen("input.txt", "r", stdin);
#endif
cin >> n;
x.resize(n);
y.resize(n);
for (int i = 0; i < n; i++) {
cin >> x[i];
}
for (int i = 0; i < n; i++) {
cin >> y[i];
}
int best = 1e9;
for (int it = 0; it < 2; it++) {
best = min(best, solve());
reverse(x.begin(), x.end());
reverse(y.begin(), y.end());
}
if (best > 1e8) {
best = 0;
}
cout << best - 1;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3700kb
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: 5636kb
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: 3692kb
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: 3612kb
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: 3640kb
input:
6 4 1 3 6 2 5 6 2 5 3 4 1
output:
13
result:
ok single line: '13'
Test #6:
score: -100
Wrong Answer
time: 0ms
memory: 3676kb
input:
6 4 1 3 3 2 5 3 2 5 3 4 1
output:
11
result:
wrong answer 1st lines differ - expected: '12', found: '11'