QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#710021 | #7956. Walk Swapping | ucup-team3646# | WA | 0ms | 3780kb | C++20 | 3.2kb | 2024-11-04 18:01:23 | 2024-11-04 18:01:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i = 0; i < ll(n); i++)
#define rep2(i,l,r) for(ll i=ll(l); i<ll(r); i++)
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
#define all(A) A.begin,A.end()
#define elif else if
using pii = pair<ll, ll>;
template<class T>
bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}
template<class T>
bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>
void print(vector<T> a) {
for (auto x : a) cerr << x << ' ';
cout << endl;
}
template<class T>
void print(T x) {
cerr << x << '\n';
}
template<class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
cerr << head << ' ';
print(forward<Tail>(tail)...);
}
vi f(int n,vi a,vi b){
vi cum(2*n+1,0);
rep(i,2*n)cum[i+1]=cum[i]+b[i%n];
vi right(2*n);
{
int r=-1;
rep(i,2*n){
if(a[i%n]==1)r=i;
right[i]=r;
}
}
return right;
vector<int>posL(n,-1);
rep(l,n){
int r=l+n-1;
int cnt=cum[r]-cum[l];
if(cnt==0)posL[l]=l;
else{
int mostR=right[r];
if(mostR-l+1==cum[mostR]-cum[l]+1)posL[l]=mostR;
}
}
return posL;
}
int inf=1<<30;
int calc(int n,vi A,vi B){
vvi pos(n,vi(n,-1));
for(int i=2*n-1;i>=0;i--){
rep(j,n){
pos[i%n][j]=pos[(i+1)%n][j];
}
pos[i%n][B[i%n]]=i%n;
}
// rep(val,n){
// cout<<"i "<<val<<" : ";print(pos[val]);
// }
int ans=inf;
rep(shift,n){
vi S(n);
rep(i,n)S[i]=A[(i+shift+n)%n];
vi T=B;
vi maru(n,0),san(n,0),batu(n,0);
int cnt_batu=0;
rep(i,n){
if(S[i]==T[i])maru[i]=1;
if(T[(i-1+n)%n]==S[i])san[i]=1;
if(maru[i]==0&&san[i]==0)batu[i]=1;
cnt_batu+=batu[i];
}
vi cum_san(2*n+1,0);
rep(i,2*n)cum_san[i+1]=cum_san[i]+san[i%n];
if(cnt_batu>=2)continue;
vi only_san(n,0),only_maru(n,0);
rep(i,n){
if(maru[i]==1&&san[i]==0)only_maru[i]=1;
if(maru[i]==0&&san[i]==1)only_san[i]=1;
}
vi L=f(n,only_san,san);
// cout<<"maru : ";print(maru);
// cout<<"san : ";print(san);
// cout<<"S : ";print(S);
// cout<<"T : ";print(T);
// cout<<"L : ";print(L);
rep2(l2,n,2*n){
if(L[l2]==-1)continue;
int pos1=L[l2]%n;
int r=pos[(pos1-shift+n)%n][S[l2%n]]+shift;
int l=l2%n;
r%=n;
int r2=r;
if(r<=l)r2+=n;
bool flag=true;
if(cum_san[r2+1]-cum_san[l+1]!=r2-l)flag=false;
if(cnt_batu==1){if(batu[l]!=1)flag=false;}
if(flag){
// print(shift,l,r2);
ans=(shift)%n*(n-1)+r2-l;
}
}
}
return ans;
}
void solve() {
int n;
cin>>n;
vi A(n),B(n);
rep(i,n){
cin>>A[i];
A[i]--;
}
rep(i,n){
cin>>B[i];
B[i]--;
}
if(A==B){
cout<<0<<endl;
return;
}
int ans1=calc(n,A,B);
reverse(A.begin(),A.end());
reverse(B.begin(),B.end());
int ans2=calc(n,A,B);
int ans=min(ans1,ans2);
if(ans==inf)ans=-1;
cout<<ans<<endl;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(0);
int T=1;
rep(i,T)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3780kb
input:
4 4 3 2 1 3 4 2 1
output:
10
result:
wrong answer 1st lines differ - expected: '1', found: '10'