実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 100 点
問題文
N 枚のカードが横一列に並んでいます。
最初、文字列 S の i 文字目が 1
のとき左から i 枚目のカードは表を向いていて、0
のとき裏を向いています。
あなたは以下の操作を 10^6 回まで行うことができます。
- 一番右にあるカードを一番左に移動する。その後、移動させたカードが表を向いているなら左から A_1,A_2,\dots,A_P 枚目のカードの表裏を全て反転させる。そして、左から B_1,B_2,\dots,B_Q 枚目のカードの表裏を全て反転させるか、何もしないかのどちらかを選択する。
操作の結果、文字列 T の i 文字目が 1
のとき左から i 枚目のカードは表を向いていて、0
のとき裏を向いているようにしたいです。
10^6 回以下の操作により条件を満たすことができるかを判定し、条件を満たすことが可能な場合は操作回数が最小となるような操作列を 1 つ出力してください。
制約
- 入力される数値は全て整数
- 1 \leq N \leq 5000
- S, T は
0
,1
のみからなる長さ N の文字列 - S \neq T
- 1 \leq P, Q \leq N
- 1 \leq A_1 < A_2 < \dots < A_P \leq N
- 1 \leq B_1 < B_2 < \dots < B_Q \leq N
入力
入力は以下の形式で標準入力から与えられる。
N S T P A_1 A_2 \dots A_P Q B_1 B_2 \dots B_Q
出力
10^6 回以下でどのように操作しても条件を満たすことができない場合、-1
を出力せよ。
条件を満たすことが可能な場合、以下の形式で操作回数が最小となるような操作列を 1 つ出力せよ。
M U
ここで M は操作回数で、U は操作列を表す長さ M の 0
, 1
のみからなる文字列である。
U の i 文字目が 1
のとき、i 回目の操作で左から B_1,B_2,\dots,B_Q 枚目のカードの表裏を全て反転させることを表し、0
のときは何もしないことを表す。
入力例 1
5 00001 00111 3 1 2 3 2 3 5
出力例 1
4 1001
1 度目の操作において、まず一番右のカードを一番左に移すとカードの状態は 10000
になり、移動させたカードが表を向いているため、左から A_1,A_2,A_3 枚目(1,2,3 枚目)のカードの表裏を全て反転させて 01100
になります。その後、左から B_1,B_2 枚目(3,5 枚目)のカードの表裏を全て反転させることを選択すれば 01001
になります。
以後も出力例に従って操作すると、2 回目の操作で 01000
に、3 回目の操作で 00100
に、4 回目の操作で 00111
になります。
これよりも操作回数が少ない方法は存在しないため、出力例は正しい出力です。
入力例 2
4 0110 1000 2 1 2 4 1 2 3 4
出力例 2
-1
どのように操作しても 10^6 回以下で条件を満たすことができないため、-1
を出力します。