QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#710235 | #7956. Walk Swapping | ucup-team3646 | WA | 3ms | 3880kb | C++20 | 2.8kb | 2024-11-04 19:09:20 | 2024-11-04 19:09:22 |
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;
// assert(pr==i);
int d = (pr - i + N) % N;
int r = nextval[pr][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 << " " << shift * (N - 1) + r - i << 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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
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: 3852kb
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: 3556kb
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: 3560kb
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: 3856kb
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: 3560kb
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: 3852kb
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: 3628kb
input:
5 4 3 5 2 1 1 3 5 4 2
output:
2
result:
ok single line: '2'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
5 4 3 5 2 1 1 4 3 5 2
output:
4
result:
ok single line: '4'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
5 1 1 1 2 1 2 1 1 1 1
output:
2
result:
ok single line: '2'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
4 4 3 2 1 1 3 2 4
output:
1
result:
ok single line: '1'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
4 4 3 2 1 1 3 4 2
output:
2
result:
ok single line: '2'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
10 2 3 1 1 3 4 5 5 6 1 1 1 3 4 5 3 5 1 7 2
output:
-1
result:
ok single line: '-1'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
5 1 4 5 3 2 5 3 2 1 4
output:
8
result:
ok single line: '8'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
5 1 2 3 4 5 5 2 1 3 4
output:
3
result:
ok single line: '3'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3452kb
input:
10 1 2 3 4 5 6 7 8 9 10 8 4 2 3 1 5 7 6 9 10
output:
-1
result:
ok single line: '-1'
Test #17:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
10 1 2 3 2 2 2 1 1 1 1 2 1 1 1 1 1 2 2 3 2
output:
41
result:
ok single line: '41'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
10 1 1 1 2 2 4 4 4 2 2 1 1 2 2 4 4 2 2 1 4
output:
12
result:
ok single line: '12'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
12 3 3 3 2 2 2 4 4 2 2 1 3 3 3 2 2 4 4 2 2 2 1 3 3
output:
13
result:
ok single line: '13'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
12 3 3 2 2 2 2 4 4 2 2 1 2 2 2 2 2 4 4 2 2 2 1 3 3
output:
19
result:
ok single line: '19'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
12 3 3 2 4 2 2 4 4 2 2 1 2 2 2 2 2 4 4 2 2 4 1 3 3
output:
-1
result:
ok single line: '-1'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
20 3 4 4 5 1 2 3 2 5 1 1 5 3 2 4 5 1 2 3 5 2 3 5 4 4 5 1 2 3 2 5 3 1 1 5 3 2 4 5 1
output:
49
result:
ok single line: '49'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
20 3 4 4 5 1 2 3 2 5 1 1 5 3 2 4 5 1 2 3 5 3 2 3 4 5 1 2 3 5 4 4 5 1 2 3 2 5 1 1 5
output:
158
result:
ok single line: '158'
Test #24:
score: 0
Accepted
time: 2ms
memory: 3852kb
input:
100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 99 1...
output:
109
result:
ok single line: '109'
Test #25:
score: 0
Accepted
time: 3ms
memory: 3880kb
input:
100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 100 ...
output:
89
result:
ok single line: '89'
Test #26:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 51 5...
output:
4924
result:
ok single line: '4924'
Test #27:
score: 0
Accepted
time: 2ms
memory: 3652kb
input:
100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 51 5...
output:
4905
result:
ok single line: '4905'
Test #28:
score: 0
Accepted
time: 2ms
memory: 3848kb
input:
100 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 6 6 6 6 6 7 7 7 7 7 8 8 8 8 8 9 9 9 9 9 10 10 10 10 10 11 11 11 11 11 12 12 12 12 12 13 13 13 13 13 14 14 14 14 14 15 15 15 15 15 16 16 16 16 16 17 17 17 17 17 18 18 18 18 18 19 19 19 19 19 20 20 20 20 20 9 9 9 9 9 10 10 10 10 10 11 11 11 11 11 1...
output:
3990
result:
ok single line: '3990'
Test #29:
score: -100
Wrong Answer
time: 2ms
memory: 3676kb
input:
100 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 ...
output:
126
result:
wrong answer 1st lines differ - expected: '125', found: '126'