ARC110 C - Exoswap

鹿島建設プログラミングコンテスト2020（AtCoder Regular Contest 110）　C- Exoswap

問題

C - Exoswap

1,2,…,Nを並び替えた数列 があります。

あなたは Pに対して、以下の N−1種類の操作を、任意の順番でちょうど 1回ずつ行わなければなりません。

P1と P2
を入れ替える
P2と P3
を入れ替える
⋮
P[N−1] と P[N]を入れ替える操作の順番を適切に決めることで、Pを昇順に並び替えてください。 もしそれが不可能な場合、-1 を出力してください。

考察

左端から順に見ていって順番と不一致の場合，一致するまで左に移動することを繰り返す方法を考えました。
After Contest で追加されたケースがWAになります。
もう少し悩んでみます。

提出コード

#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
int main(){
  int n;
  cin>>n;
  int P[n];
  rep(i,n){
    cin>>P[i];
    P[i]-=1;
  }
  int cur=0;
  int cnt=0;
  vector<int>vec;
  while(1){
    if(cnt>n){
      cout<<-1<<endl;
      return 0;
    }
    if(cur==n) break;
    if(P[cur]==cur){
      cur++;
      continue;
    }
    for(int i=cur;i<n;i++){
      if(P[i]==cur){
        for(int j=i;j>cur;j--){
          cnt++;
          vec.push_back(j);
          P[j]=P[j-1];
        }
        P[cur]=cur;
        cur++;
        break;
      }
    }
  }
  if(cnt != n-1){
    cout<<-1<<endl;
    return 0;
  }
  for(auto e:vec){
    cout<<e<<endl;
  }
  return 0;
}

更に考察

操作は各Nについてちょうど 1回ずつおこなわなければならない，とあるので，mapを使って重複をチェックしてみたところ，ACしました。

ACしたコード

#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
int main(){
  int n;
  cin>>n;
  int P[n];
  rep(i,n){
    cin>>P[i];
    P[i]-=1;
  }
  int cur=0;
  int cnt=0;
  vector<int>vec;
  map<int,int>mp;
  while(1){
    if(cnt>n){
      cout<<-1<<endl;
      return 0;
    }
    if(cur==n) break;
    if(P[cur]==cur){
      cur++;
      continue;
    }
    for(int i=cur;i<n;i++){
      if(P[i]==cur){
        for(int j=i;j>cur;j--){
          cnt++;
          vec.push_back(j);
          mp[j]++;
          P[j]=P[j-1];
        }
        P[cur]=cur;
        cur++;
        break;
      }
    }
  }
  if(cnt != n-1){
    cout<<-1<<endl;
    return 0;
  }
  for(auto e:mp){
    if(e.second !=1){
      cout<<-1<<endl;
      return 0;
    }
  } 
  for(auto e:vec){
    cout<<e<<endl;
  }
  return 0;
}