/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
すぬけくんは，0 と 1 からなる長さ N の整数列 a=(a_1,a_2,\cdots,a_N) と，空の整数列 b を持っています． a の初期状態は入力で与えられ，a_i=S_i です．
すぬけくんは，以下の 3 種類の操作を好きな順番で好きな回数行えます．
-
a を右シフトする．つまり，a を (a_N,a_1,a_2,\cdots,a_{N-1}) で置き換える．
-
a を左シフトする．つまり，a を (a_2,a_3,\cdots,a_N,a_1) で置き換える．
-
b の末尾に現在の a_1 の値を追加する．
長さ M の整数列 T=(T_1,T_2,\cdots,T_M) が与えられます． b を T に一致させることができるか判定し，可能な場合は必要な操作回数の最小値を求めてください．
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 0 \leq S_i \leq 1
- 0 \leq T_i \leq 1
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる．
N M S_1 S_2 \cdots S_N T_1 T_2 \cdots T_M
出力
b を T に一致させることが不可能な場合，-1 を出力せよ．
可能な場合は，必要な操作回数の最小値を出力せよ．
入力例 1
3 4 0 0 1 0 1 1 0
出力例 1
6
以下のように 6 回操作すればよいです．
-
b の末尾に現在の a_1 の値を追加する．b=(0) となる．
-
a を右シフトする．a=(1,0,0) となる．
-
b の末尾に現在の a_1 の値を追加する．b=(0,1) となる．
-
b の末尾に現在の a_1 の値を追加する．b=(0,1,1) となる．
-
a を右シフトする．a=(0,1,0) となる．
-
b の末尾に現在の a_1 の値を追加する．b=(0,1,1,0) となる．
入力例 2
1 1 0 1
出力例 2
-1
Score : 300 points
Problem Statement
Snuke has a sequence of N integers a=(a_1,a_2,\cdots,a_N) consisting of 0s and 1s, and an empty integer sequence b. The initial state a_i=S_i is given to you as input.
Snuke can do the following three operations any number of times in any order.
-
Shift a to the right. In other words, replace a with (a_N,a_1,a_2,\cdots,a_{N-1}).
-
Shift a to the left. In other words, replace a with (a_2,a_3,\cdots,a_N,a_1).
-
Append the current value of a_1 at the end of b.
You are also given a sequence of M integers T=(T_1,T_2,\cdots,T_M). Determine whether it is possible to make b equal to T. If it is possible, find the minimum number of operations needed to do so.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 0 \leq S_i \leq 1
- 0 \leq T_i \leq 1
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M S_1 S_2 \cdots S_N T_1 T_2 \cdots T_M
Output
If it is impossible to make b equal to T, print -1.
If it is possible, print the minimum number of operations needed to do so.
Sample Input 1
3 4 0 0 1 0 1 1 0
Sample Output 1
6
The following sequence of six operations will do the job.
-
Append the current value of a_1 at the end of b, making b=(0).
-
Shift a to the right, making a=(1,0,0).
-
Append the current value of a_1 at the end of b, making b=(0,1).
-
Append the current value of a_1 at the end of b, making b=(0,1,1).
-
Shift a to the right, making a=(0,1,0).
-
Append the current value of a_1 at the end of b, making b=(0,1,1,0).
Sample Input 2
1 1 0 1
Sample Output 2
-1