QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#341681 | #7956. Walk Swapping | ucup-team2981# | WA | 1ms | 3628kb | C++20 | 2.2kb | 2024-02-29 20:31:01 | 2024-02-29 20:31:03 |
Judging History
answer
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>
using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;
void Hollwo_Pelw();
signed main(){
#ifndef hollwo_pelw_local
if (fopen(".inp", "r"))
assert(freopen(".inp", "r", stdin)), assert(freopen(".out", "w", stdout));
#else
using namespace chrono;
auto start = steady_clock::now();
#endif
cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
int testcases = 1;
// cin >> testcases;
for (int test = 1; test <= testcases; test++){
// cout << "Case #" << test << ": ";
Hollwo_Pelw();
}
#ifdef hollwo_pelw_local
auto end = steady_clock::now();
cout << "\nExecution time : " << duration_cast<milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}
const int N = 3005;
int n, a[N], b[N], c[N], match[N], res = 2e9;
inline int get(int l, int r) {
if (l <= r)
return match[r] - (l ? match[l - 1] : 0);
return get(l, n - 1) + get(0, r);
}
void solve() {
for (int p = 0; p < n; p++) {
for (int i = 0; i < n; i++)
c[i] = a[(i + p) % n];
// cout << "P = " << p << '\n';
// for (int i = 0; i < n; i++)
// cout << c[i] << " \n"[i == n - 1];
// for (int i = 0; i < n; i++)
// cout << b[i] << " \n"[i == n - 1];
int move = (n - 1) * p;
vector<int> pos;
for (int i = 0; i < n; i++) {
if (b[i] != c[i])
pos.push_back(i);
match[i] = c[(i + 1) % n] == b[i] + (i == 0 ? 0 : match[i - 1]);
}
for (int i = 0; i < (int) pos.size(); i++) {
int l = pos[(i + 1) % pos.size()], r = pos[i] % n; // check if path from l -> r can make b == c
// cout << l << " -> " << r << '\n';
int diff = (r - l + n) % n;
// cout << get(l + r) + (c[l] == b[r]) << diff << '\n';
if (get(l, (r + n - 1) % n) + (c[l] == b[r]) == diff + 1)
res = min(res, diff + move);
}
if (pos.empty())
res = min(res, move);
}
}
void Hollwo_Pelw(){
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
cin >> b[i];
}
for (int turn = 2; turn --; ) {
solve();
reverse(a, a + n);
reverse(b, b + n);
}
cout << (res == 2e9 ? -1 : res) << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3616kb
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: 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: 1ms
memory: 3628kb
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: 3608kb
input:
4 1 2 3 4 4 2 1 3
output:
2
result:
ok single line: '2'
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 3592kb
input:
6 4 1 3 6 2 5 6 2 5 3 4 1
output:
-1
result:
wrong answer 1st lines differ - expected: '13', found: '-1'