← 返回题目列表

Codeforces · 2217/E

E. 绝对更大

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

给你一个从 $$$1$$$ 到 $$$n$$$ 的整数排列 $$$p$$$$$^{\text{∗}}$$$。

对于长度为 $$$n$$$ 的任意排列 $$$q$$$,我们说索引 $$$j$$$ 占主导地位 索引 $$$i$$$ 当且仅当满足以下所有条件时:

  • $$$j \gt i$$$,
  • $$$p_j \gt p_i$$$,并且
  • $$$q_j \gt q_i$$$。

还给您一个长度为 $$$n$$$ 的数组 $$$d$$$,其中 $$$d_i$$$ 表示主导索引 $$$i$$$ 的索引数量。

你的任务是构造一个从 $$$1$$$ 到 $$$n$$$ 的整数排列 $$$q$$$,这样对于每个索引 $$$i$$$ ($$$1 \le i \le n$$$),支配 $$$i$$$ 的索引 $$$j$$$ 的数量恰好是 $$$d_i$$$。

如果存在这样的$$$q$$$,则输出任何有效的。否则报告不存在。

$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$个不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5000$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$。保证 $$$p$$$ 形成从 $$$1$$$ 到 $$$n$$$ 的整数排列。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$d_1, d_2, \ldots, d_n$$$ ($$$0 \le d_i \le n$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$。

输出

对于每个测试用例:

  • 如果可以构造 $$$q$$$,则输出一行包含 $$$n$$$ 整数 $$$q_1, q_2, \ldots, q_n$$$ — 一个有效的排列。如果存在多个有效答案,您可以输出其中任何一个。
  • 否则,输出$$$-1$$$。

示例

输入
复制

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

输出
复制

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

注意

在第一个测试用例中,有效输出为 $$$q = [1, 2, 3]$$$:

  • 对于 $$$i=1$$$,我们有 $$$p_1=2$$$ 和 $$$q_1=1$$$。索引 $$$j=2$$$ 支配 $$$i=1$$$,因为 $$$2 \gt 1$$$、$$$p_2=3 \gt p_1$$$ 和 $$$q_2=2 \gt q_1$$$。索引 $$$j=3$$$ 不支配 $$$i=1$$$,因为 $$$p_3=1 \lt p_1$$$。因此,恰好 $$$1$$$ 索引支配 $$$i=1$$$,它匹配 $$$d_1=1$$$。
  • 对于 $$$i=2$$$,我们有 $$$p_2=3$$$ 和 $$$q_2=2$$$。唯一较大的索引是 $$$j=3$$$,但 $$$p_3=1 \lt p_2$$$,因此它不占主导地位。因此,$$$0$$$ 索引支配$$$i=2$$$,匹配$$$d_2=0$$$。
  • 对于 $$$i=3$$$,没有更大的索引 $$$j \gt 3$$$,因此 $$$0$$$ 索引占主导地位,匹配 $$$d_3=0$$$。

在第二个测试用例中,$$$p = [3, 4, 1, 2]$$$ 和 $$$d = [2, 1, 1, 0]$$$。让我们看看$$$i=2$$$,其中$$$p_2=4$$$。由于不存在索引 $$$j \gt 2$$$ 和 $$$p_j \gt p_2$$$,因此没有索引可以支配 $$$i=2$$$。然而,数组 $$$d$$$ 需要 $$$d_2=1$$$,这使得无法构造有效的排列 $$$q$$$。因此,答案是 -1.