/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 500 点
問題文
いま、電光掲示板に 0 と 1 から成る長さ N の文字列 S が表示されています。
あなたは次の操作を何回でも行うことができます。なお、ここでは電光掲示板に表示されている文字列の i (1 \leq i \leq N) 文字目を S_i と表します。
操作 整数 (l, r) (1 \leq l < r \leq N) であって、次の条件のうちいずれかを満たすものを 1 組選び、S_l と S_r を入れ替える。
- S_l=
0かつ S_{l+1}=\cdots=S_r=1を満たす。- S_{l}=\cdots=S_{r-1}=
1かつ S_r=0を満たす。
電光掲示板に表示されている文字列を T に一致させることができるか判定し、可能な場合は操作回数として考えられる最小の値を求めてください。
制約
- 2 \leq N \leq 500000
- S は
0と1からなる長さ N の文字列である - T は
0と1からなる長さ N の文字列である
入力
入力は以下の形式で標準入力から与えられます。
N S T
出力
電光掲示板に表示されている文字列を T にすることが不可能な場合は、-1 を出力してください。
可能な場合は、操作回数として考えられる最小の値を出力してください。
入力例 1
7 1110110 1010111
出力例 1
2
例えば以下のように操作を行えば、2 回の操作で電光掲示板に表示されている文字列を 1010111 にすることができます。
- (l, r) = (2, 4) を選んで操作を行う。そのとき、電光掲示板の文字列は
1110110から1011110に変化する。 - (l, r) = (4, 7) を選んで操作を行う。そのとき、電光掲示板の文字列は
1011110から1010111に変化する。
入力例 2
20 11111000000000011111 11111000000000011111
出力例 2
0
操作を行う前の時点で、電光掲示板に表示されている文字列が T であるため、答えは 0 となります。
入力例 3
6 111100 111000
出力例 3
-1
どのように操作を行っても、電光掲示板に文字列 T を表示させることが不可能な場合は、-1 と出力してください。
入力例 4
119 10101111011101001011111000111111101011110011010111111111111111010111111111111110111111110111110111101111111111110111011 11111111111111111111111111011111101011111011110111110010100101001110111011110111111111110010011111101111111101110111011
出力例 4
22
Score: 500 points
Problem Statement
An electric bulletin board is showing a string S of length N consisting of 0 and 1.
You can do the following operation any number of times, where S_i denotes the i-th character (1 \leq i \leq N) of the string shown in the board.
Operation: choose a pair of integers (l, r) (1 \leq l < r \leq N) satisfying one of the conditions below, and swap S_l and S_r.
- S_l=
0and S_{l+1}=\cdots=S_r=1.- S_{l}=\cdots=S_{r-1}=
1and S_r=0.
Determine whether it is possible to make the string shown in the board match T, and find the minimum number of operations needed if it is possible.
Constraints
- 2 \leq N \leq 500000
- S is a string of length N consisting of
0and1. - T is a string of length N consisting of
0and1.
Input
Input is given from Standard Input in the following format:
N S T
Output
If it is impossible to make the board show the string T, print -1.
If it is possible, find the minimum number of operations needed.
Sample Input 1
7 1110110 1010111
Sample Output 1
2
Here is one possible way to make the board show the string 1010111 in two operations:
- Do the operation with (l, r) = (2, 4), changing the string in the board from
1110110to1011110. - Do the operation with (l, r) = (4, 7), changing the string in the board from
1011110to1010111.
Sample Input 2
20 11111000000000011111 11111000000000011111
Sample Output 2
0
The board already shows the string T before doing any operation, so the answer is 0.
Sample Input 3
6 111100 111000
Sample Output 3
-1
If there is no sequence of operations that makes the board show the string T, print -1.
Sample Input 4
119 10101111011101001011111000111111101011110011010111111111111111010111111111111110111111110111110111101111111111110111011 11111111111111111111111111011111101011111011110111110010100101001110111011110111111111110010011111101111111101110111011
Sample Output 4
22