ARC110 C - Exoswap

問題

atcoder.jp

解法

• 各数字を目的の位置に移動させるためには、素直にswapするしかない。
• 1から順番にswapしていけばいい。いくら他の数字をswapしていも、結局1を1番目にするという操作は必要。
• 得られた操作手順を確認し、重複がある場合やちょうどn-1回でない場合は-1を返す。

コード

int main() {
  int n;
  cin >> n;
  vi p(n), ip(n), flag(n, 0), ans;
  rep(i, n) {
    cin >> p[i];
    p[i]--;
    ip[p[i]] = i;
  }
  for (int i = 0; i < n; i++) {
    for (int j = ip[i]; j > i; j--) {
      ip[p[j - 1]]++;
      ip[p[j]]--;
      swap(p[j], p[j - 1]);
      ans.push_back(j);
    }
    if (sz(ans) >= n) {
      cout << -1 << endl;
      return 0;
    }
  }
  rep(i, n) {
    if (p[i] != i) {
      cout << -1 << endl;
      return 0;
    }
  }
  if (sz(ans) != n - 1) {
    cout << -1 << endl;
    return 0;
  }
  for (auto e : ans) {
    if (flag[e]) {
      cout << -1 << endl;
      return 0;
    }
    flag[e] = 1;
  }
  for (auto e : ans) cout << e << endl;
  return 0;
}