QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#711708 | #7956. Walk Swapping | kizen# | WA | 0ms | 3856kb | C++20 | 3.1kb | 2024-11-05 13:07:05 | 2024-11-05 13:07:06 |
Judging History
answer
#include <bits/stdc++.h>
#ifndef LOCAL
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#endif
#define sz(v) ((int)v.size())
#define all(v) v.begin(), v.end()
#define pb push_back
#define pi array<int, 2>
#define comp(v) (sort(all(v)), v.erase(unique(all(v)), v.end()))
#define lb(v, x) (lower_bound(all(v), x) - v.begin())
#define MIN(x, y) (x = min(x, y))
using namespace std;
#define int long long
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n; cin >> n;
// n = 3000;
vector<int> a(n), inb(n);
for(int i = 0; i < n; ++i){
cin >> a[i];
// a[i] = 1;
--a[i];
}
for(int i = 0; i < n; ++i){
cin >> inb[i];
// inb[i] = 1;
--inb[i];
}
if(n == 1){
cout << (a[0] == inb[0] ? 0 : -1);
return 0;
}
else if(n == 2){
if(a == inb) cout << 0;
else if(a[0] == inb[1] && a[1] == inb[0]) cout << 1;
else cout << -1;
return 0;
}
int ans = (int)1e18;
for(int rr = 0; rr < 2; ++rr){
auto b = inb;
for(int i = 0; i < n; ++i){
b.pb(b[i]);
}
vector<vector<int>> pos(n);
for(int i = 0; i < n * 2; ++i){
pos[b[i]].pb(i);
}
auto sol2 = [&](vector<int> x){
for(int i = 0; i < n; ++i) x.pb(x[i]);
int same = 0;
for(int i = 0; i < n; ++i){
if(x[i] == b[i]){
same = 1;
break;
}
}
if(!same) return (int)1e18;
int sp = 0, rp = 0;
int rv = (int)1e18;
for(int i = n - 1; i >= 0; --i){
if(x[i] != b[i]){
sp = i;
break;
}
}
for(int i = 0; i < n; ++i){
if(x[i + n - 1] != b[i + n - 1]) sp = i + n - 1;
rp = max(rp, i);
while(rp + 1 < n * 2 && b[rp] == x[rp + 1]){
++rp;
}
int l = max(i + 1, sp), r = min(rp, i + n - 2);
if(l <= r){
int p = lb(pos[x[i]], l);
if(p < sz(pos[x[i]]) && pos[x[i]][p] <= r){
// cout << i << ' ' << pos[x[i]][p] << endl;
MIN(rv, pos[x[i]][p] - i);
}
}
}
return rv;
};
auto sol1 = [&](vector<int> x){
for(int rep = 1; rep < n; rep += n - 2){
for(int i = 0, now = 0; i < n; ++i){
MIN(ans, now + sol2(x));
now += n - 1;
rotate(x.begin(), x.begin() + rep, x.end());
}
if(n <= 2) break;
}
};
sol1(a);
reverse(all(a));
reverse(all(inb));
}
if(ans == (int)1e18) ans = -1;
cout << ans << '\n';
// cout << clock() / (double)CLOCKS_PER_SEC;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3620kb
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: 3648kb
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: 3772kb
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: 3560kb
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: 3848kb
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: 3564kb
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: 3548kb
input:
5 4 3 5 2 1 1 3 5 4 2
output:
2
result:
ok single line: '2'
Test #9:
score: -100
Wrong Answer
time: 0ms
memory: 3848kb
input:
5 4 3 5 2 1 1 4 3 5 2
output:
-1
result:
wrong answer 1st lines differ - expected: '4', found: '-1'