QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#760567 | #7956. Walk Swapping | SanguineChameleon | TL | 268ms | 823624kb | C++20 | 2.5kb | 2024-11-18 17:37:00 | 2024-11-18 17:37:01 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
void justDoIt();
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
justDoIt();
return 0;
}
const int INF = 1e9 + 20;
const long long BASE = 1e4 + 3;
const long long MOD = 5e6 + 7;
void calc(vector<long long>& a, vector<vector<long long>>& shifts) {
int n = a.size();
// shifts[i][j] is clockwise
for (int i = 0; i < n; i++) {
vector<long long> rem(n - 1);
for (int j = 0; j < n - 1; j++) {
rem[j] = a[(i + 1 + j) % n];
}
long long h = 0;
for (int j = 0; j < n - 1; j++) {
h = (h * BASE + rem[j]) % MOD;
}
long long pw = 1;
for (int j = 0; j < n - 2; j++) {
pw = pw * BASE % MOD;
}
for (int j = 0; j < n - 1; j++) {
shifts[i][j] = h;
h = (h + MOD - (pw * rem[j]) % MOD) % MOD;
h = (h * BASE + rem[j]) % MOD;
}
}
}
int solve(vector<long long> a, vector<long long> b) {
int n = a.size();
if (n == 1) {
if (a[0] == b[0]) {
return 0;
}
else {
return INF;
}
}
vector<vector<long long>> shiftsA(n, vector<long long>(n - 1));
vector<vector<long long>> shiftsB(n, vector<long long>(n - 1));
calc(a, shiftsA);
calc(b, shiftsB);
vector<vector<long long>> f(n, vector<long long>(MOD, -1));
for (int i = 0; i < n; i++) {
for (int j = 1; j < n - 1; j++) {
f[i][shiftsB[i][j]] = n - 1 - j;
}
f[i][shiftsB[i][0]] = 0;
}
int res = INF;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int dist = (j + n - i) % n;
long long h = shiftsA[i][dist % (n - 1)];
int it = f[j][h];
if (it != -1) {
res = min(res, dist + it * n);
}
}
}
return res;
}
void justDoIt() {
int n;
cin >> n;
vector<long long> a(n), b(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
cin >> b[i];
}
int res = INF;
for (int iter = 0; iter < 2; iter++) {
res = min(res, solve(a, b));
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
}
if (res == INF) {
cout << -1;
return;
}
else {
cout << res;
return;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 55ms
memory: 198552kb
input:
4 4 3 2 1 3 4 2 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 70ms
memory: 276776kb
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: 91ms
memory: 276728kb
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: 55ms
memory: 198516kb
input:
4 1 2 3 4 4 2 1 3
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 75ms
memory: 276576kb
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: 59ms
memory: 276596kb
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: 60ms
memory: 198468kb
input:
4 4 3 2 1 1 3 2 4
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 63ms
memory: 237480kb
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: 48ms
memory: 237464kb
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: 55ms
memory: 237688kb
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: 49ms
memory: 198572kb
input:
4 4 3 2 1 1 3 2 4
output:
1
result:
ok single line: '1'
Test #12:
score: 0
Accepted
time: 56ms
memory: 198708kb
input:
4 4 3 2 1 1 3 4 2
output:
2
result:
ok single line: '2'
Test #13:
score: 0
Accepted
time: 118ms
memory: 432872kb
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: 60ms
memory: 237508kb
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: 65ms
memory: 237672kb
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: 111ms
memory: 432872kb
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: 135ms
memory: 432712kb
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: 116ms
memory: 432800kb
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: 150ms
memory: 511048kb
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: 136ms
memory: 511056kb
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: 175ms
memory: 511196kb
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: 236ms
memory: 823620kb
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: 268ms
memory: 823624kb
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: -100
Time Limit Exceeded
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...