🐷

ARC 110 | C - Exoswap

2020/12/06に公開

問題

考えたこと

1から順番に移動して記録していけばいい。
この操作が行えない場合はそもそも移動できないということである。
その際にすでに移動していたパターンがあれば移動できないので-1を出力する。
操作が終わったあとにソートされているか確認し、操作回数もあっていればそれが答えである。

コード

実装時のTips

各数値のインデックスはmapに保存しておく

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

// 数字を小さい方から動かしていく
int main() {
  ll n;
  cin >> n;
  unordered_map<int, int> mp;  // {数値, idx}
  vector<int> p(n);
  for (int i = 0; i < n; i++) {
    cin >> p[i];
    p[i]--;
    mp[p[i]] = i;
  }
  vector<bool> done(n);
  // 操作を行う
  vector<int> ans;
  for (int i = 0; i < n; i++) {
    while (mp[i] != i) {
      ll right = mp[i];
      ll left = right - 1;
      if (done[left]) break;
      swap(p[left], p[right]);
      mp[p[left]] = left;
      mp[p[right]] = right;
      done[left] = true;
      ans.push_back(left);
    }
  }
  // check
  for (int i = 0; i < n; i++) {
    if (p[i] != i) {
      cout << -1 << endl;
      return 0;
    }
  }
  if ((n - 1) != ans.size()) {
    cout << -1 << endl;
    return 0;
  };
  for (int i = 0; i < ans.size(); i++) {
    cout << ans[i] + 1 << endl;
  }
}

ARC 110 | C - Exoswap

問題

考えたこと

コード

参考

Discussion