QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#710208 | #7956. Walk Swapping | ucup-team3646 | RE | 0ms | 3844kb | C++20 | 2.7kb | 2024-11-04 19:04:33 | 2024-11-04 19:04:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool deb = 0;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<int> A(N), B(N);
for (int i = 0; i < N; i++) {
cin >> A[i];
A[i]--;
}
for (int i = 0; i < N; i++) {
cin >> B[i];
B[i]--;
}
int an = 1e9 + 10;
for (int tu = 0; tu < 2; tu++) {
vector<vector<int>> nextval(N);
vector<int> pos(N, -1);
for (int i = 2 * N - 1; i >= 0; i--) {
pos[B[i % N]] = i % N;
if (i < N)nextval[i] = pos;
}
for (int shift = 0; shift < N; shift++) {
int res = 1e9 + 10;
vector<int> SA(N);
for (int i = 0; i < N; i++)SA[i] = A[(i + shift) % N];
vector<int> DB(N, 0);
vector<vector<int>> sum(2 * N + 1, vector<int>(4, 0));
vector<vector<int>> prevbit(N);
for (int i = 0; i < N; i++) {
if (SA[i] == B[i])DB[i]++;
if (SA[i] == B[(i + N - 1) % N])DB[i] += 2;
}
if (deb)for (int i = 0; i < N; i++)cout << SA[i] << " \n"[i == N - 1];
if (deb)for (int i = 0; i < N; i++)cout << DB[i] << " \n"[i == N - 1];
vector<int> posbit(4, -1);
for (int i = 0; i < 2 * N; i++) {
posbit[DB[i % N]] = i % N;
if (i >= N)prevbit[i % N] = posbit;
}
for (int i = 0; i < N * 2; i++) {
for (int j = 0; j < 4; j++)sum[i + 1][j] = sum[i][j];
sum[i + 1][DB[i % N]]++;
}
if (sum[2 * N][0] > 2) {
continue;
}
for (int i = 0; i < N; i++) {
if (sum[2 * N][0] == 2 && DB[i] != 0)continue;
int pr = prevbit[i][2];
assert(pr!=-1);
if (pr == -1)pr = i;
int d = (pr - i + N) % N;
int r = nextval[pr][SA[i]];
//r -= shift;
//r %= N;
//if (r < N)r += N;
d += (r - pr + N) % N;
if (d >= N)continue;
if (r < i)r += N;
if (sum[r + 1][2] + sum[r + 1][3] - sum[i + 1][2] - sum[i + 1][3] != r - i)continue;
if (deb)cout << shift << ":" << i << " " << r << " " << shift * (N - 1) + r - i << endl;
an = min(an, shift * (N - 1) + r - i);
}
}
reverse(A.begin(), A.end());
reverse(B.begin(), B.end());
if (deb)cout << "return" << endl;
}
cout << (an < 1e9 ? an : -1) << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3844kb
input:
4 4 3 2 1 3 4 2 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3612kb
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: 3552kb
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: 3552kb
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: 3780kb
input:
6 4 1 3 6 2 5 6 2 5 3 4 1
output:
13
result:
ok single line: '13'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
6 4 1 3 3 2 5 3 2 5 3 4 1
output:
12
result:
ok single line: '12'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
4 4 3 2 1 1 3 2 4
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
5 4 3 5 2 1 1 3 5 4 2
output:
2
result:
ok single line: '2'
Test #9:
score: -100
Runtime Error
input:
5 4 3 5 2 1 1 4 3 5 2