🐷

ARC 110 | C - Exoswap

1 min read

問題

https://atcoder.jp/contests/arc110/tasks/arc110_c

考えたこと

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;
  }
}

参考

https://atcoder.jp/contests/arc110/editorial/387

Discussion

ログインするとコメントできます