QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#527956 | #7956. Walk Swapping | JooDdae | WA | 1ms | 3648kb | C++20 | 1.2kb | 2024-08-23 00:18:17 | 2024-08-23 00:18:18 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;
int n, a[6060], b[6060], r[6060];
vector<int> find(int a[], int L, int R) {
vector<int> re;
for(int i=L;i<=R;i++) re.push_back(a[i]);
return re;
}
int solve() {
for(int i=1;i<=n;i++) a[n+i] = a[i], b[n+i] = b[i];
r[n+n+1] = n+n;
for(int i=n+n;i>=1;i--) r[i] = (a[i] == b[i] ? r[i+1] : i-1);
int re = INF;
for(int i=1;i<=n;i++) {
int L = i, R = i+n-1;
int M = r[L];
if(a[M+1] == b[R] && find(a, M+2, R) == find(b, M+1, R-1)) re = min(re, R-M-1);
}
return re;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=1;i<=n;i++) cin >> b[i];
int ans = INF;
for(int i=1;i<n;i++) {
ans = min(ans, solve() + n*min(i-1, n-i));
rotate(a+1, a+2, a+1+n);
}
rotate(a+1, a+2, a+1+n);
reverse(a+1, a+1+n), reverse(b+1, b+1+n);
for(int i=1;i<=n;i++) {
ans = min(ans, solve() + n*min(i-1, n-i));
rotate(a+1, a+2, a+1+n);
}
cout << (ans == INF ? -1 : ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3536kb
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: 0ms
memory: 3588kb
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: 3648kb
input:
4 1 2 3 4 4 2 1 3
output:
2
result:
ok single line: '2'
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3540kb
input:
6 4 1 3 6 2 5 6 2 5 3 4 1
output:
14
result:
wrong answer 1st lines differ - expected: '13', found: '14'