← 返回题目列表

Codeforces · 2084/F

F. 天空景观

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

给你一个长度为 $$$n$$$$$^{\text{*}}$$$ 的排列 $$$a$$$。

我们说长度 $$$n$$$ 的排列 $$$b$$$ 是 好 如果执行以下操作后两个排列 $$$a$$$ 和 $$$b$$$ 可以变得相同 最多 $$$n$$$ 次 (可能为零):

  • 选择两个整数 $$$l, r$$$,使得 $$$1 \le l \lt r \le n$$$ 和 $$$a_r = \min(a_l, a_{l + 1}, \ldots, a_r)$$$。
  • 循环将子段 $$$[a_l, a_{l + 1}, \ldots, a_r]$$$ 向右移动一位。换句话说,将 $$$a$$$ 替换为 $$$[a_1, \ldots, a_{l - 1}, \; a_r, a_l, a_{l + 1}, \ldots, a_{r - 1}, \; a_{r + 1}, \ldots, a_n]$$$。

您还会得到一个长度为 $$$n$$$ 的排列 $$$c$$$,其中缺少一些元素并用 $$$0$$$ 表示。

你需要找到一个 好 排列 $$$b_1, b_2, \ldots, b_n$$$ 使得 $$$b$$$ 可以通过填充 $$$c$$$ 的缺失元素来形成(即,对于所有 $$$1 \le i \le n$$$,如果 $$$c_i \ne 0$$$,则 $$$b_i = c_i$$$)。如果不可能,则输出$$$-1$$$。

$$$^{\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 10^4$$$)。测试用例的描述如下。

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

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$)。保证 $$$a$$$ 是长度 $$$n$$$ 的排列。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$c_1, c_2, \ldots, c_n$$$ ($$$0 \le c_i \le n$$$)。保证 $$$c$$$ 中不是 $$$0$$$ 的元素是不同的。

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

输出

对于每个测试用例:

  • 如果不可能找到这样好的排列$$$b$$$,则输出单个整数$$$-1$$$。
  • 否则,输出 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ — 您找到的良好排列 $$$b$$$。您需要确保对于所有$$$1 \le i \le n$$$,如果$$$c_i \ne 0$$$,则$$$b_i = c_i$$$。如果有多个答案,则输出其中任何一个。

示例

输入
复制

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

输出
复制

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

注意

在第一个测试用例中,$$$b = [1, 2]$$$ 是有效答案,因为执行以下操作后,$$$a$$$ 和 $$$b$$$ 将变得相同:

  • 选择 $$$l = 1, r = 2$$$ 并将子段 $$$[a_1, a_2]$$$ 向右循环移动一位。那么 $$$a$$$ 将变为 $$$[1, 2]$$$。

在第二个测试用例中,$$$b = [2, 3, 4, 1]$$$ 是有效答案,因为执行以下操作后,$$$a$$$ 和 $$$b$$$ 将变得相同:

  • 选择 $$$l = 1, r = 2$$$ 并将子段 $$$[a_1, a_2]$$$ 向右循环移动一位。那么 $$$a$$$ 将变为 $$$[2, 3, 4, 1]$$$。

在第三个测试用例中,$$$b = [1, 3, 2, 4, 5]$$$ 是有效答案,因为执行以下操作后,$$$a$$$ 和 $$$b$$$ 将变得相同:

  • 选择 $$$l = 1, r = 3$$$ 并将子段 $$$[a_1, a_2, a_3]$$$ 向右循环移动一位。那么 $$$a$$$ 将变为 $$$[1, 3, 2, 5, 4]$$$。
  • 选择 $$$l = 4, r = 5$$$ 并将子段 $$$[a_4, a_5]$$$ 向右循环移动一位。那么 $$$a$$$ 将变为 $$$[1, 3, 2, 4, 5]$$$。

在第四个测试用例中, $$$b = [3, 2, 1, 5, 4]$$$ 是有效答案,因为 $$$a$$$ 和 $$$b$$$ 已经相同。

在第五个测试用例中,不可能找到这么好的排列$$$b$$$,所以你应该输出$$$-1$$$。

在第六个测试用例中, $$$b = [3, 2, 1, 5, 4, 6]$$$ 是有效答案,因为执行以下操作后, $$$a$$$ 和 $$$b$$$ 将变得相同:

  • 选择 $$$l = 2, r = 4$$$ 并将子段 $$$[a_2, a_3, a_4]$$$ 向右循环移动一位。那么 $$$a$$$ 将变成 $$$[3, 2, 5, 6, 1, 4]$$$。
  • 选择 $$$l = 3, r = 5$$$ 并将子段 $$$[a_3, a_4, a_5]$$$ 向右循环移动一位。那么 $$$a$$$ 将变为 $$$[3, 2, 1, 5, 6, 4]$$$。
  • 选择 $$$l = 5, r = 6$$$ 并将子段 $$$[a_5, a_6]$$$ 向右循环移动一位。那么 $$$a$$$ 将变为 $$$[3, 2, 1, 5, 4, 6]$$$。