K - 門松
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
(1,2,\ldots,N) の順列 P=(P_1,P_2,\ldots,P_N) と 0,1 からなる長さ N-1 の数列 C が与えられます。
ここで、与えられる順列 P は以下の条件を満たすことが保証されます。
- 整数 i\ (1 \le i \le N-1) について、 i が奇数ならば P_i < P_{i+1} を、 i が偶数ならば P_i > P_{i+1} を満たす。
あなたは、最初すべての要素が -1 である長さ N-1 の数列 b を用意して、以下の二種類の操作を任意の順番で 300000 回以下任意の回数行うことができます。
- type 1 : 整数 i\ (1 \le i \le N-1) を選ぶ。 P_i と P_{i+1} を swap する。
- type 2 : 整数 i\ (1 \le i \le N-1) を選ぶ。 P_i < P_{i+1} ならば b_i = 0, P_i > P_{i+1} ならば b_i=1 と置き換える。
b=C とすることが可能か判定し、可能ならば操作方法を一つ示してください。
制約
- 2 \leq N \leq 2 \times 10^{5}
- P は (1,2,\ldots, N) の順列
- 整数 i\ (1 \le i \le N-1) について、 i が奇数ならば P_i < P_{i+1} 、 i が偶数ならば P_i > P_{i+1}
- C_i \in \lbrace 0,1 \rbrace \ (1 \le i \le N-1)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
P_1 P_2 \ldots P_N
C_1 C_2 \ldots C_{N-1}
出力
b=C とすることが不可能な場合は、 -1 と一行に出力せよ。
b=C とすることが可能な場合は、操作回数を M として、以下の形式で出力せよ。
M T_1 I_1 T_2 I_2 \vdots T_M I_M
ただし、 T_k は k 回目の操作において type T_k を選ぶことを表し、 I_k は k 回目の操作において i=I_k とすることを表す。
入力例 1
4 3 4 1 2 0 0 0
出力例 1
4 2 1 2 3 1 2 2 2