https://beta.atcoder.jp/contests/arc103/tasks/arc103_c
考察過程
1. 実験してみると、作れる最低条件が3つ見つかる
2. 「S[0]は1」「S[N-1]は0」「Sの[0,N-2]は回分になっている」
3. これ以外なら作れると仮定して考える
4. 1なら普通に辺を伸ばせば大丈夫
5. 0なら分岐させる必要がある
6. これで全部作れそう?
解法
https://beta.atcoder.jp/contests/arc103/submissions/3309244
「S[0]は1」「S[N-1]は0」「Sの[0,N-2]は回分になっている」場合に構築ができる。
なので、以上の条件を満たさない場合は-1として答えよう。
先頭N-1個の文字を見て、
1なら「辺を伸ばして先頭を移動させる」、
0なら「今の頂点にくっつける形で辺を伸ばして先頭はそのまま」
という方針で辺を張っていく。
これだけでAC
string S; int N; //--------------------------------------------------------------------------------------------------- void _main() { cin >> S; N = S.length(); if (S.front() == '0' or S.back() == '1') { printf("-1\n"); return; } rep(i, 0, (N - 1) / 2) if (S[i] != S[N - 2 - i]) { printf("-1\n"); return; } vector<pair<int, int>> ans; int top = 0; rep(i, 0, N - 1) { ans.push_back({ top, i + 1 }); if (S[i] == '1') top = i + 1; } fore(p, ans) printf("%d %d\n", p.first + 1, p.second + 1); }