QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#710015#7956. Walk Swappingucup-team3646#WA 0ms3628kbC++203.2kb2024-11-04 17:58:442024-11-04 17:58:50

Judging History

你现在查看的是最新测评结果

  • [2024-11-04 17:58:50]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3628kb
  • [2024-11-04 17:58:44]
  • 提交

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=(n-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;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3628kb

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: 3508kb

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: 3508kb

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: 3564kb

input:

4
1 2 3 4
4 2 1 3

output:

2

result:

ok single line: '2'

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3560kb

input:

6
4 1 3 6 2 5
6 2 5 3 4 1

output:

11

result:

wrong answer 1st lines differ - expected: '13', found: '11'