QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#296215 | #7956. Walk Swapping | defyers# | WA | 1ms | 3616kb | C++17 | 2.2kb | 2024-01-02 14:38:03 | 2024-01-02 14:38:04 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
using ll = long long;
using pii = pair<int, int>;
using ull = unsigned long long;
const ull X = 2748283;
void solve(int TC) {
int n;
cin >> n;
ll ans = 1e9;
vector<ull> a(n), b(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
cin >> b[i];
}
vector<ull> pwr(n + 1);
pwr[0] = 1;
for (int i = 1; i < n; i++) {
pwr[i] = pwr[i - 1] * X;
}
unordered_map<ull, int> rotate;
rotate.reserve(8192);
{
ull H = 0;
for (int i = 0; i < n; i++) {
H = H * X + b[i];
}
// cout << "@ " << H << endl;
rotate[H] = 0;
for (int i = 0; i < n; i++) {
H = (H - pwr[n - 1] * b[i]) * X + b[i];
rotate[H] = min(i + 1, n - (i + 1));
}
}
ull oH = 0;
for (int i = 0; i < n; i++) {
oH = oH * X + a[i];
}
if (rotate.count(oH)) {
ans = min(ans, rotate[oH] * ll(n - 1));
}
for (int i = 0; i < n; i++) {
ull H = oH;
vector<ull> A = a;
// cout << "!" << oH << endl;
for (int j = 1; j <= n; j++) {
int x = (i + j) % n;
int p = (i + j - 1) % n;
H -= A[p] * pwr[n - 1 - p];
H -= A[x] * pwr[n - 1 - x];
swap(A[p], A[x]);
H += A[p] * pwr[n - 1 - p];
H += A[x] * pwr[n - 1 - x];
// cout << "forward: ";
// for (int j = 0; j < n; j++) {
// cout << A[j] << " ";
// }
// cout << " hash: " << H;
// cout << endl;
if (rotate.count(H)) {
ans = min(ans, j + rotate[H] * ll(n - 1));
}
}
H = oH;
A = a;
for (int j = 1; j <= n; j++) {
int x = (i - j + n) % n;
int p = (i - j + n + 1) % n;
H -= A[p] * pwr[n - 1 - p];
H += A[x] * pwr[n - 1 - x];
swap(A[p], A[x]);
// cout << "backward: ";
// for (int j = 0; j < n; j++) {
// cout << A[j] << " ";
// }
// cout << endl;
if (rotate.count(H)) {
ans = min(ans, j + rotate[H] * ll(n - 1));
}
}
}
if (ans == 1e9) {
cout << -1 << "\n";
}
else {
cout << ans << "\n";
}
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cout << fixed << setprecision(10);
int t = 1;
// cin >> t;
for (int i = 1; i <= t; i++) {
solve(i);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
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: 1ms
memory: 3540kb
input:
6 4 1 3 6 2 5 6 2 1 3 4 5
output:
-1
result:
ok single line: '-1'
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 3508kb
input:
4 1 2 3 4 4 2 1 3
output:
4
result:
wrong answer 1st lines differ - expected: '2', found: '4'