/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
以下では、0 と 1 のみからなる文字列を 01 列と呼びます。
2 つの長さ N の 01 列 S, T が与えられます。 下記の条件を満たす長さ N の 01 列 U のうち辞書順最小のものを出力してください。
- S と U のハミング距離は、T と U のハミング距離に等しい。
ただし、そのような長さ N の 01 列 U が存在しない場合は、代わりに -1 を出力してください。
ハミング距離とは？
01 列 X = X_1X_2\ldots X_N と 01 列 Y = Y_1Y_2\ldots Y_N のハミング距離は、X_i \neq Y_i を満たす整数 1 \leq i \leq N の個数です。
辞書順とは？
01 列 X = X_1X_2\ldots X_N が 01 列 Y = Y_1Y_2\ldots Y_N より辞書順で小さいとは、下記の 2 つの条件をともに満たす整数 1 \leq i \leq N が存在することを言います。
- X_1X_2\ldots X_{i-1} = Y_1Y_2\ldots Y_{i-1}
- X_i =
0かつ Y_i =1
制約
- 1 \leq N \leq 2 \times 10^5
- N は整数
- S, T は長さ N の 01 列
入力
入力は以下の形式で標準入力から与えられる。
N S T
出力
問題文中の条件を満たす長さ N の 01 列 U のうち辞書順最小のものを出力せよ。 ただし、そのような 01 列 U が存在しない場合は、代わりに -1 を出力せよ。
入力例 1
5 00100 10011
出力例 1
00001
U = 00001とおくと、S と U のハミング距離と、T と U のハミング距離はどちらも 2 です。
また、これが問題文中の条件を満たす長さ N の 01 列 U のうち辞書順最小です。
入力例 2
1 0 1
出力例 2
-1
問題文中の条件を満たす長さ N の 01 列 U が存在しないため、-1 を出力します。
Score : 300 points
Problem Statement
Below, a 01-sequence is a string consisting of 0 and 1.
You are given two 01-sequences S and T of length N each. Print the lexicographically smallest 01-sequence U of length N that satisfies the condition below.
- The Hamming distance between S and U equals the Hamming distance between T and U.
If there is no such 01-sequence U of length N, print -1 instead.
What is Hamming distance?
The Hamming distance between 01-sequences X = X_1X_2\ldots X_N and Y = Y_1Y_2\ldots Y_N is the number of integers 1 \leq i \leq N such that X_i \neq Y_i.
What is lexicographical order?
A 01-sequence X = X_1X_2\ldots X_N is lexicographically smaller than a 01-sequence Y = Y_1Y_2\ldots Y_N when there is an integer 1 \leq i \leq N that satisfies both of the conditions below.
- X_1X_2\ldots X_{i-1} = Y_1Y_2\ldots Y_{i-1}.
- X_i =
0and Y_i =1.
Constraints
- 1 \leq N \leq 2 \times 10^5
- N is an integer.
- S and T are 01-sequences of length N each.
Input
The input is given from Standard Input in the following format:
N S T
Output
Print the lexicographically smallest 01-sequence U of length N that satisfies the condition in the Problem Statement, or -1 if there is no such 01-sequence U.
Sample Input 1
5 00100 10011
Sample Output 1
00001
For U = 00001, the Hamming distance between S and U and the Hamming distance between T and U are both 2.
Additionally, this is the lexicographically smallest 01-sequence U of length N that satisfies the condition.
Sample Input 2
1 0 1
Sample Output 2
-1
No 01-sequence U of length N satisfies the condition, so -1 should be printed.