\(x\) の先頭から \(2,4,6,\cdots\) 項目を flip して得られる列 \(y\) を考えます． \(A\) の \(2,4,6,\cdots\) 項目も flip しておき，\(y\) を \(A\) に一致させることを目標にします．

\(x\) に対する操作を，\(y\) に対する操作で言い換えてみると，以下のようになります．

• 操作A: \(y\) の先頭に \(0\) を追加する．
• 操作B: \(y\) の末尾に値を追加する．追加する値は，操作前の \(y\) の長さの偶奇に依存し，偶数なら \(0\)，奇数なら \(1\) になる．

まず明らかに，\(A_1=0\) であることが必要です． 次に，\(A\) の要素がすべて \(0\) なら，明らかに答えは可能です．

そうでない時，\(A\) の中でもっとも先頭に近い \(1\) が \(A_z\) だとします． \(A_z\) およびそれより後ろの部分を取り出し，\(S\) と名前をつけることにします． 操作Bだけを行うことで \(S\) を作ることを考えます． このとき，\(S\) が \((0,1,0,1,...)\) (長さ \(N\)) の部分列であることが必要です． 逆にこの条件を満たせば，\((0,1,0,1,\cdots)\) のうちで \(S\) に対応するところでは操作B，そうでないところでは操作Aを行うことで，\(y\) を \(A\) に一致させることができます．

以上の処理は \(O(N)\) で実装することができます．

解答例(c++)