QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#673983 | #7956. Walk Swapping | AMATSUKAZE# | WA | 1ms | 3688kb | C++20 | 2.7kb | 2024-10-25 12:50:42 | 2024-10-25 12:50:43 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,s,n) for (int i = (int)(s); i < (int)(n); i++)
#define all(v) begin(v),end(v)
using namespace std;
using ll = long long;
bool chmin(auto &a, auto b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto &a, auto b) { return a < b ? a = b, 1 : 0; }
const ll mod = (1LL<<61)-1;
ll BASE ;
ll B[6500];
ll mul(ll a, ll b){
return static_cast<ll>((__int128)a * b % mod);
}
// concat a, b, where c is length of b
ll concat(ll a, ll b, ll c) {
return (mul(a, B[c]) + b) % mod;
}
ll get(ll a, ll b, ll c) {
return (a - mul(b, B[c]) + mod) % mod;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
random_device seed_gen;
mt19937 engine(seed_gen());
uniform_int_distribution<ll> dist(1LL<<40, 1LL<<50);
BASE = dist(engine);
B[0] = 1;
rep(i,0,6499){
B[i+1] = mul(B[i], BASE);
}
int n; cin >> n;
vector<int> a(n), b(n);
rep(i,0,n) cin >> a[i];
rep(i,0,n) cin >> b[i];
int d = -1;
rep(i,1,n+1) {
if (n % i != 0) continue;
bool mode = 1;
rep(j,0,n){
if (b[j] != b[j%i]) mode = 0;
}
if (mode) {
d = i;
break;
}
}
unordered_map<ll,int> mp;
vector<ll> roriha_b(2*n+1);
rep(i,0,2*n) {
roriha_b[i+1] = concat(roriha_b[i], b[i%n], 1);
}
rep(i,0,d){
ll targ = get(roriha_b[i+n], roriha_b[i], n);
mp[targ] = i;
}
int ans = 1e9;
rep(i,0,n){
vector<ll> a_tmp(n);
vector<ll> roriha(n+1);
int cnt = 0;
rep(j,0,n){
if (i == j) continue;
a_tmp[cnt++] = a[j];
}
a_tmp.back() = a_tmp.front();
rep(j,0,n){
roriha[j+1] = concat(roriha[j], a_tmp[j], 1);
}
int tar = i;
int mode = 0;
rep(j,0,n-1){
int l = mode;
int m = mode + tar;
int r = mode + n-1;
ll val = concat(get(roriha[m], roriha[l], tar), a[i], 1);
val = concat(val, get(roriha[r], roriha[m], n-1-tar), n-1-tar);
if (mp.find(val) != mp.end()) {
int gogo = mp[val];
int step_pos = j;
int step_neg = (n-j)%n;
chmin(ans, step_pos + (n-1) * (((-gogo)%d+d)%d) );
chmin(ans, step_neg + (n-1) * (gogo%d)) ;
}
tar += 1;
if (tar >= n){
tar = 0;
mode = 1;
}
}
}
if (ans > 9e8){
cout << -1 << '\n';
}else{
cout << ans << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3656kb
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: 3584kb
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: 3580kb
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: 0ms
memory: 3688kb
input:
4 1 2 3 4 4 2 1 3
output:
6
result:
wrong answer 1st lines differ - expected: '2', found: '6'