Incomplete Permutation [第八回 アルゴリズム実技検定 F]

https://atcoder.jp/contests/past202109-open/tasks/past202109_f

• 構築

解説

https://atcoder.jp/contests/past202109-open/submissions/26602840

構築問題。
構築問題の基本は、シンプルな構築ルールである。
なるべく簡単に簡単に条件を満たせるルールを使うことが大切。

-1のとき

構築できない場合はどういった場合かを考えてみると、0が1つの場合になる。
0が1つであるので、他はすべて1ということになる。
1の部分は添え字と同じ数字になっている必要があるが、そうすると、0の部分で使える数字は
その添え字の数字しかなくなり、添え字と違う数字を割り当てることができない。

構築できない場合をざっくり考えてみると他に無さそうではある。
（構築法を考えると、0が1つのときだけだなという確信が増してくる）

どういった構築ルールにするか

適当に並び替えてやれば条件を満たしそうではあるが、それは人間視点であり、
どんな状況でも単一ルールで条件を満たすようなものを考えてみよう。

自分は0の部分の添え字を1つずつ横にずらすことで、自分の添え字とは違うようにした。
実装ではdequeを使った実装を行った。
1つずつ横にずらす必要があるので、順番にdequeに入れておいて、そのあと、
先頭の1つを取り出して、末尾に追加してやれば1つずらしたような感じになる。

int N;
string S;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;
    
    deque<int> zero, one;
    rep(i, 0, N) {
        if (S[i] == '0') zero.push_back(i + 1);
        else one.push_back(i + 1);
    }

    if (zero.size() == 0) { }
    else if (zero.size() == 1) {
        cout << -1 << endl;
        return;
    }
    else {
        int top = zero.front();
        zero.pop_front();
        zero.push_back(top);
    }

    rep(i, 0, N) {
        if (i) printf(" ");
        if (S[i] == '0') {
            printf("%d", zero.front());
            zero.pop_front();
        }
        else {
            printf("%d", one.front());
            one.pop_front();
        }
    }
    printf("\n");
}