ARC 178

Mon, Jul 7, 2025

https://atcoder.jp/contests/arc178

A. Good Permutation 2

https://atcoder.jp/contests/arc178/tasks/arc178_a

自力 AC.

$A$ の順序は問題に答えに影響しないので昇順にソートしておく。

$A$ の中に $1$ または $N$ が含まれている場合は、どのようにしても良い順列を作れないので -1 を出力する。

それ以外のときは $P_{A_i} = A_i + 1$ とし、確定していない部分は小さい順にまだ使用していない数字で埋めれば良い。

$A_1 = x$ のときで考えてみる。

辞書順で最小にしたいのでなるべく $1, 2, \cdots$ の順にしたいが $1, 2, \cdots, x$ とすると良い順列にならないので最初の $x$ 個は $1, 2, \cdots, x-1, x+1$ とするのが最適である。同様にして $P_{A_i} = A_i + 1$ としておけば良い順列の条件を満たす辞書順最小の順列が得られる。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, M;
    cin >> N >> M;
    vll A(M);
    rep(i, M) cin >> A[i];

    {
        int ok = 1;
        rep(i, M) {
            if (A[i] == 1 || A[i] == N) ok = 0;
        }
        if (!ok) {
            cout << -1 << endl;
            return;
        }
    }

    vll ans(N + 1, -1);
    vint used(N + 1);
    for (int a : A) {
        ans[a] = a + 1;
        used[a + 1] = 1;
    }

    queue<int> que;
    rep2(i, 1, N + 1) {
        if (!used[i]) que.push(i);
    }

    rep2(i, 1, N + 1) {
        if (ans[i] < 0) {
            ans[i] = que.front();
            que.pop();
        }
    }

    ans.erase(ans.begin(), ans.begin() + 1);
    print(ans);
}