C - Conditional Swap
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
きつねが一列に並んでいますが,順番を入れ替わるときには周囲を気にするそうです.
問題文
(1,2,\ldots,N) の順列 P=(P_1,P_2,\ldots,P_N) と Q=(Q_1,Q_2,\ldots,Q_N) が与えられる.以下の操作を高々 N^2 回行って P を Q に一致させられるか判定し,可能な場合はそのような操作列を 1 通り求めよ.
- 次の条件のうち少なくとも一方を満たす整数 i を選び,P_i と P_{i+1} の値を入れ替える.
- 1 \leq i \leq N-2 かつ \min(P_i,P_{i+1}) < P_{i+2} < \max(P_i,P_{i+1})
- 2 \leq i \leq N-1 かつ \min(P_i,P_{i+1}) < P_{i-1} < \max(P_i,P_{i+1})
制約
- 2 \leq N \leq 1000.
- (P_1,P_2,\ldots,P_N) は (1,2,\ldots,N) の順列である.
- (Q_1,Q_2,\ldots,Q_N) は (1,2,\ldots,N) の順列である.
入力
入力は以下の形式で標準入力から与えられる.
N P_1 P_2 \cdots P_N Q_1 Q_2 \cdots Q_N
出力
P を Q に一致させられる場合,以下の形式で操作列を出力せよ.
k i_1 i_2 \cdots i_k
ここで,k は操作の回数 (0 \leq k \leq N^2) であり,i_j は j 回目の操作で i=i_j を選ぶことを表す.
P を Q に一致させられない場合,-1
と出力せよ.
入力例 1
3 2 1 3 2 3 1
出力例 1
1 2
入力例 2
3 1 2 3 1 3 2
出力例 2
-1