J - Complicated Operations
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1200 点
問題文
長さ N の数列 S_{0} と T が与えられます。 ここで、N はある自然数 r に対して 2^{r} と表せることが保証されます。
あなたは 0 回以上 500 回以内、操作を行うことができます。あなたの目的は操作回数を k として S_{k} と T を一致させることです。
i 回目の操作は以下のようにして行われます。
- 0 \leq x < i, 0\leq y < i を満たす整数 x,y、-(N-1) \leq f \leq N-1 を満たす整数 f を指定する
- その後、
x
,y
のみからなる長さ N の文字列 s を指定する - x,y,f,s を用いて長さ N の数列 S_{i} を作る
- S_{i,j} は s_{j} が
x
ならば、S_{x,j} となる - S_{i,j} は s_j が
y
ならば、S_{y,j-f} となる。ただし、1 \leq j-f \leq N を満たさなくてはならない
- S_{i,j} は s_{j} が
目的が達成可能かどうか判定し、可能ならば、操作の一例を出力してください。不可能ならば代わりに -1
を出力してください。
操作についてはサンプル 1 も参照してください。
制約
- 2 \leq N \leq 8192
- 1 \leq S_{0,j},T_{j} \leq N
- N はある自然数 r に対して 2^{r} と表せる
- 与えられる入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N S_{0,1} S_{0,2} ... S_{0,N} T_{1} T_{2} ... T_{N}
出力
目的が達成不可能な場合は -1 を出力せよ。
目的が達成可能な場合は以下の形式で操作を出力せよ。操作が問題文中の制約を満たし、S_{K} が T と一致したならば正解となる。
K x_1 y_1 f_1 s_1 : x_K y_K f_K s_K
入力例 1
4 1 2 3 4 2 4 3 4
出力例 1
2 0 0 1 xxyx 0 1 -2 yyxx
- 1 回目の操作では x=0,y=0,f=1,s=
xxyx
を指定して操作を行います - S_{1,1},S_{1,2},S_{1,4} はそれぞれ S_{0,1},S_{0,2},S_{0,4} に、S_{1,3} は S_{0,2} となります。よって S_{1}=(1,2,2,4) となります
- 2 回目の操作では x=0,y=1,f=-2,s=
yyxx
を指定して操作を行います - S_{2,3},S_{2,4} はそれぞれ S_{0,3},S_{0,4} となり、S_{2,1},S_{2,2} はそれぞれ S_{1,3},S_{1,4} となります。よって S_{2}=(2,4,3,4) となります
- S_{2} と T が一致したため正解です
入力例 2
4 3 1 2 3 1 2 3 4
出力例 2
-1
- 目的が達成不可能な場合は
-1
を出力してください