[AtCoder] ARC 110 C – Exoswap
問題
方針
\( 1 \) から \( N \) まで順番に交換ソートしていくことを考えます。自然数 \( i \) がどの場所にいるかという配列を管理することで効率よくソートできます。
コード
#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; int P[N]; int d[N]; for (int i = 0; i < N; i++) { cin >> P[i]; P[i]--; d[P[i]] = i; } int ans[N - 1]{}; bool flag[N - 1]{}; int id = 0; for (int i = 0; i < N - 1; i++) { if (d[i] == i) continue; if (d[i] < i) { for (int j = d[i]; j < i; j++) { if (flag[j]) { cout << "-1\n"; return 0; } flag[j] = true; ans[id] = j; swap(P[j], P[j + 1]); swap(d[P[j]], d[P[j + 1]]); id++; if (id == N - 1) break; } } else { for (int j = d[i]; j > i; j--) { if (flag[j - 1]) { cout << "-1\n"; return 0; } flag[j - 1] = true; ans[id] = j - 1; swap(P[j - 1], P[j]); swap(d[P[j - 1]], d[P[j]]); id++; if (id == N - 1) break; } } } if (id != N - 1) { cout << "-1\n"; return 0; } for (int i = 0; i < N; i++) { if (P[i] != i) { cout << "-1\n"; return 0; } } for (int i = 0; i < N - 1; i++) { cout << ans[i] + 1 << "\n"; } return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません