QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#710292 | #7956. Walk Swapping | ucup-team3646 | WA | 0ms | 3856kb | C++20 | 2.8kb | 2024-11-04 19:20:08 | 2024-11-04 19:20:10 |
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];
if (pr == -1)pr = i;
int d = (pr - i + N) % N;
int r = nextval[(pr-1+N)%N][SA[i]];
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;
int cost = shift * (N - 1) + r - i;
r %= N;
int l = i;
if (l < r)l += N;
if (sum[l][0] + sum[l][2] - sum[r + 1][2] - sum[r + 1][0] != 0)continue;
if (deb)cout << shift << ":" << i << " " << r << " " << cost << endl;
an = min(an, cost);
}
}
reverse(A.begin(), A.end());
reverse(B.begin(), B.end());
if (deb)cout << "return" << endl;
}
cout << (an < 1e9 ? an : -1) << endl;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3508kb
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: 3856kb
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: 3664kb
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: 3632kb
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: 3628kb
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: 3564kb
input:
6 4 1 3 3 2 5 3 2 5 3 4 1
output:
13
result:
wrong answer 1st lines differ - expected: '12', found: '13'