← 返回题目列表

Codeforces · 2065/E

E. 斯基比杜斯和里兹

中文机器翻译题面 查看原题

随着情人节的临近,斯基比杜斯迫切需要一种方法来激怒他的暗恋对象!幸运的是,他知道方法:创建完美的二进制字符串!

给定一个二进制字符串$$$^{\text{*}}$$$ $$$t$$$,让$$$x$$$代表$$$t$$$中$$$\texttt{0}$$$的数量,$$$y$$$代表$$$t$$$中$$$\texttt{1}$$$的数量。其余额值定义为 $$$\max(x-y, y-x)$$$ 的值。

Skibidus 为您提供三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$。他请求你帮助构造一个长度为 $$$n+m$$$ 的二进制字符串 $$$s$$$,其中 $$$n$$$ $$$\texttt{0}$$$ 和 $$$m$$$ $$$\texttt{1}$$$ 使得其所有子字符串 $$$^{\text{†}}$$$ 之间的最大平衡值恰好为 $$$k$$$。如果不可能,则输出-1。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行也是唯一一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$0 \leq n, m \leq 2\cdot 10^5$$$, $$$1 \leq k \leq n + m$$$, $$$n+m\geq 1$$$)。

保证所有测试用例的 $$$n$$$ 之和与 $$$m$$$ 之和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,如果可以构造$$$s$$$,则将其输出到新行。如果有多个可能的$$$s$$$,则输出任意一个。否则,换行输出-1。

示例

输入 #1

6
1 2 1
4 3 2
2 4 3
8 3 2
5 0 4
5 0 5

输出 #1

101
0100101
011011
-1
-1
00000

注意

在第一个测试用例中,我们必须构造$$$s$$$,使其包含一个$$$\texttt{0}$$$、两个$$$\texttt{1}$$$,并且其所有子字符串之间的最大余额为$$$1$$$。一种可能的有效 $$$s$$$ 是 $$$\texttt{101}$$$,因为:

- 考虑由索引 $$$[1, 1]$$$ 界定的子字符串。其余额值为 $$$\max(0 - 1, 1 - 0) = 1$$$。
- 考虑由索引 $$$[1, 2]$$$ 界定的子字符串。其余额值为 $$$\max(1 - 1, 1 - 1) = 0$$$。
- 考虑由索引 $$$[1, 3]$$$ 界定的子字符串。其余额值为 $$$\max(1 - 2, 2 - 1) = 1$$$。
- 考虑由索引 $$$[2, 2]$$$ 界定的子字符串。其余额值为 $$$\max(1 - 0, 0 - 1) = 1$$$。
- 考虑由索引 $$$[2, 3]$$$ 界定的子字符串。其余额值为 $$$\max(1 - 1, 1 - 1) = 0$$$。
- 考虑由索引 $$$[3, 3]$$$ 界定的子字符串。其余额值为 $$$\max(0 - 1, 1 - 0) = 1$$$。

在所有可能的子字符串中,最大余额值为$$$1$$$。

在第二个测试用例中,具有最大余额值的子字符串是$$$0100$$$,其余额为$$$max(3-1, 1-3)=2$$$。