AtCoder Regular Contest 151
A
Equal Hamming Distances
AtCoder
⌀ 355
原题
←B →
翻译中…

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 =$ 0 and $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$.

翻译中…

样例

Input #1
5
00100
10011
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.
Input #2
1
0
1
Output #2
-1
No $01$-sequence $U$ of length $N$ satisfies the condition, so $-1$ should be printed.
题目信息
题号
arc151_a
时间限制
2 s
内存限制
1024 MB

题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。