← 返回题目列表

Codeforces · 2110/C

C. 赛车

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

2077 年,一项名为业余爱好无人机的运动在机器人中越来越受欢迎。

你已经拥有一架无人机,并且你想获胜。为此,您的无人机需要飞过有 $$$n$$$ 障碍物的航线。

第 $$$i$$$ 个障碍物由两个数字 $$$l_i、r_i$$$ 定义。令无人机在第 $$$i$$$ 个障碍物处的高度为 $$$h_i$$$。那么如果$$$l_i \le h_i \le r_i$$$,无人机就会穿过这个障碍物。最初,无人机在地面上,这意味着 $$$h_0 = 0$$$。

无人机的飞行程序由数组 $$$d_1, d_2, \ldots, d_n$$$ 表示,其中 $$$h_{i} - h_{i-1} = d_i$$$ 和 $$$0 \leq d_i \leq 1$$$。这意味着您的无人机要么不会改变障碍物之间的高度,要么会上升 $$$1$$$。您已经有一个飞行计划,但其中的一些 $$$d_i$$$ 未知并标记为 $$$-1$$$。将未知的 $$$d_i$$$ 替换为数字 $$$0$$$ 和 $$$1$$$ 以创建穿过整个障碍物路线的飞行程序,或者报告这是不可能的。

输入

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

在每个测试用例的第一行,给出一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5)$$$ — 数组 $$$d$$$ 的大小。

在每个测试用例的第二行中,有 $$$n$$$ 整数 $$$d_1, d_2, \ldots, d_n$$$ ($$$-1 \leq d_i \leq 1$$$) — 数组 $$$d$$$ 的元素。 $$$d_i = -1$$$ 意味着这个$$$d_i$$$ 对你来说是未知的。

接下来,有 $$$n$$$ 行包含 $$$2$$$ 整数 $$$l_i,r_i$$$ ($$$0\leq l_i\leq r_i\leq n$$$) — 障碍物的描述。

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

输出

对于每个测试用例,如果可以正确恢复数组 $$$d$$$,则输出 $$$n$$$ 整数 $$$d_1,d_2,\ldots,d_n$$$,如果不可能,则输出 $$$-1$$$。

示例

输入
复制

5
4
0 -1 -1 1
0 4
1 2
2 4
1 4
3
0 -1 -1
0 1
2 2
0 3
2
-1 -1
0 0
2 2
8
-1 -1 1 -1 -1 0 0 -1
0 0
0 1
0 2
0 2
1 3
0 4
2 5
4 5
1
0
1 1

输出
复制

0 1 1 1 
-1
-1
0 1 1 0 1 0 0 1 
-1

注意

在第一个测试用例中,一个可能的答案是 $$$d=[0,1,1,1]$$$。数组 $$$h$$$ 将是 $$$[0,0+1,0+1+1,0+1+1+1]=[0,1,2,3]$$$。该数组满足问题的条件。

在第二个测试用例中,可以证明不存在合适的数组$$$d$$$,所以答案是$$$-1$$$。