← 返回题目列表

Codeforces · 1981/C

C. 海龟和不完整的序列

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

Turtle 正在玩一个由正整数组成的序列 $$$a_1, a_2, \ldots, a_n$$$。不幸的是,一些整数在玩的时候丢失了。

现在序列变得不完整。可能存在任意数量的索引$$$i$$$,使得$$$a_i$$$ 变为$$$-1$$$。令新序列为$$$a'$$$。

乌龟很伤心。但 Turtle 记得,对于从 $$$1$$$ 到 $$$n - 1$$$ 的每个整数 $$$i$$$,$$$a_i = \left\lfloor\frac{a_{i + 1}}{2}\right\rfloor$$$ 或 $$$a_{i + 1} = \left\lfloor\frac{a_i}{2}\right\rfloor$$$ 都适用于原始序列$$$a$$$。

海龟希望你帮助他完成序列。但有时海龟会犯错误,所以如果你无法完成序列,你需要告诉他。

正式地,您需要找到另一个由正整数组成的序列 $$$b_1, b_2, \ldots, b_n$$$ ,使得:

- 对于从 $$$1$$$ 到 $$$n$$$ 的每个整数 $$$i$$$,如果 $$$a'_i \ne -1$$$,则 $$$b_i = a'_i$$$。
- 对于从 $$$1$$$ 到 $$$n - 1$$$ 的每个整数 $$$i$$$,$$$b_i = \left\lfloor\frac{b_{i + 1}}{2}\right\rfloor$$$ 或 $$$b_{i + 1} = \left\lfloor\frac{b_i}{2}\right\rfloor$$$ 成立。
- 对于从 $$$1$$$ 到 $$$n$$$ 的每个整数 $$$i$$$,$$$1 \le b_i \le 10^9$$$。

如果不存在满足上述所有条件的序列$$$b_1, b_2, \ldots, b_n$$$,则需要​​报告$$$-1$$$。

输入

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

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

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a'_1, a'_2, \ldots, a'_n$$$ ($$$a'_i = -1$$$ 或 $$$1 \le a'_i \le 10^8$$$) — 序列 $$$a'$$$ 的元素。

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

输出

对于每个测试用例,如果没有满足所有条件的序列$$$b_1, b_2, \ldots, b_n$$$,则输出单个整数$$$-1$$$。

否则,输出 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ — 您找到的序列 $$$b_1, b_2, \ldots, b_n$$$ 的元素。对于从 $$$1$$$ 到 $$$n$$$ 的每个整数 $$$i$$$,该序列应满足 $$$1 \le b_i \le 10^9$$$。如果有多个答案,请打印其中任何一个。

示例

输入 #1

9
8
-1 -1 -1 2 -1 -1 1 -1
4
-1 -1 -1 -1
6
3 -1 -1 -1 9 -1
4
-1 5 -1 6
4
2 -1 -1 3
4
1 2 3 4
2
4 2
5
-1 3 -1 3 6
13
-1 -1 3 -1 -1 -1 -1 7 -1 -1 3 -1 -1

输出 #1

4 9 4 2 4 2 1 2
7 3 6 13
3 1 2 4 9 18
-1
-1
-1
4 2
6 3 1 3 6
3 1 3 1 3 7 3 7 3 1 3 1 3

注意

在第一个测试用例中, $$$[4, 2, 1, 2, 1, 2, 1, 3]$$$ 也可以是答案,而 $$$[4, 2, 5, 10, 5, 2, 1, 3]$$$ 和 $$$[4, 2, 1, 2, 1, 2, 1, 4]$$$不能。

在第二个测试用例中,$$$[1, 2, 5, 2]$$$ 也可以是答案。

从第四个到第六个测试用例,可以看出没有答案,所以应该输出$$$-1$$$。