# AGC032-A Limited Insertion

##### tags: `構築練習`

## 問題情報

https://atcoder.jp/contests/agc032/tasks/agc032_a

diff: 738

## 考えたこと

$i = N, N - 1, \dots, 1$ の順に、$i$番目に行われた操作を考える。明らかに$b_j = j$を満たすような$j$が候補であるが、そのような$j (= s)$の中で最大のものが$i$番目に行われた操作であると断定できる。

なぜなら、そうで無いと仮定した時、 $i - 1$番目までの操作をした時点で$b_{s - 1} = s$であり、$s$は挿入できないのに$b$に存在していることになり、矛盾している。

各回の操作を特定できたので、それを出力すればOK。

## 提出コード

void Main() {
    usize N; input(N);
    std::vector<u32> b(N); input(b);
    std::vector<u32> ans;
    for (u32 i{} ; i < N ; i++) {
        u32 last{(u32)supi};
        for (u32 j{} ; j < N - i ; j++) {
            if (b[j] == j + 1) last = j;
        }
        if (last == (u32)supi) {
            out(-1);
            return;
        }
        ans.push_back(last + 1);
        b.erase(b.begin() + last);
    }
    std::reverse(ans.begin(), ans.end());
    for (auto a : ans) out(a);
}

かかった時間: 18分