← 返回题目列表

Codeforces · 1991/C

C. 绝对零

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

给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。

在一次操作中,您将执行以下两步移动:

1. 选择一个整数 $$$x$$$ ($$$0 \le x \le 10^{9}$$$)。
2. 将每个 $$$a_i$$$ 替换为 $$$|a_i - x|$$$,其中 $$$|v|$$$ 表示 $$$v$$$ 的绝对值。

例如,选择$$$x = 8$$$,则数组$$$[5, 7, 10]$$$将变为$$$[|5-8|, |7-8|, |10-8|] = [3,1,2]$$$。

构造一个操作序列,使$$$a$$$的所有元素在最多$$$40$$$操作中等于$$$0$$$,或者确定这是不可能的。您不需要最小化操作数量。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。

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

输出

对于每个测试用例,如果在最多 $$$40$$$ 操作中不可能使所有数组元素等于 $$$0$$$,则输出单个整数 $$$-1$$$。

否则,输出两行。输出的第一行应包含一个整数 $$$k$$$ ($$$0 \le k \le 40$$$) - 操作数。输出的第二行应包含 $$$k$$$ 整数 $$$x_1, x_2, \ldots, x_k$$$ ($$$0 \le x_i \le 10^{9}$$$) - 操作序列,表示在第 $$$i$$$ 操作中,您选择了 $$$x=x_i$$$。

如果有多个解,则输出其中任意一个。

您不需要最小化操作次数。

示例

输入 #1

5
1
5
2
0 0
3
4 6 8
4
80 40 20 10
5
1 2 3 4 5

输出 #1

1
5
0

3
6 1 1
7
60 40 20 10 30 25 5
-1

注意

在第一个测试用例中,我们只能执行一个操作,选择 $$$x = 5$$$,将数组从 $$$[5]$$$ 更改为 $$$[0]$$$。

在第二个测试用例中,不需要任何操作,因为数组的所有元素都已经是 $$$0$$$。

在第三个测试用例中,我们可以选择 $$$x = 6$$$ 将数组从 $$$[4, 6, 8]$$$ 更改为 $$$[2, 0, 2]$$$,然后选择 $$$x = 1$$$ 将其更改为 $$$[1, 1, 1]$$$,最后再次选择 $$$x = 1$$$ 更改数组变成 $$$[0, 0, 0]$$$。

在第四个测试用例中,我们可以按照$$$(60, 40, 20, 10, 30, 25, 5)$$$的操作顺序将所有元素$$$0$$$。

在第五个测试用例中,可以证明在最多$$$40$$$操作中不可能使所有元素$$$0$$$。因此,输出为$$$-1$$$。