← 返回题目列表

Codeforces · 1418/B

B. 负前缀

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

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

数组的每个位置 $$$i$$$ ($$$1 \le i \le n$$$) 要么被锁定,要么被解锁。您可以获取解锁位置上的值,以任意顺序重新排列它们,然后将它们放回解锁位置。您不得删除任何值、添加新值或重新排列锁定位置上的值。您可以将这些值保留为原来的顺序。

例如让$$$a = [-1, 1, \underline{3}, 2, \underline{-2}, 1, -4, \underline{0}]$$$,下划线位置被锁定。可以获得以下数组:

- $$$[-1, 1, \underline{3}, 2, \underline{-2}, 1, -4, \underline{0}]$$$;
- $$$[-4, -1, \underline{3}, 2, \underline{-2}, 1, 1, \underline{0}]$$$;
- $$$[1, -1, \下划线{3}, 2, \下划线{-2}, 1, -4, \下划线{0}]$$$;
- $$$[1, 2, \下划线{3}, -1, \下划线{-2}, -4, 1, \下划线{0}]$$$;
- 以及其他一些。

设$$$p$$$为数组$$$a$$$重新排列后的前缀和序列。所以$$$p_1 = a_1$$$,$$$p_2 = a_1 + a_2$$$,$$$p_3 = a_1 + a_2 + a_3$$$,$$$\dots$$$,$$$p_n = a_1 + a_2 + \dots + a_n$$$。

设 $$$k$$$ 为最大值 $$$j$$$ ($$$1 \le j \le n$$$),使得 $$$p_j < 0$$$。如果不存在 $$$j$$$ 使得 $$$p_j < 0$$$,则 $$$k = 0$$$。

您的目标是以 $$$k$$$ 尽可能小的方式重新排列值。

输出重新排列后的数组 $$$a$$$,使其值 $$$k$$$ 尽可能最小。如果有多个答案,则打印其中任何一个。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 数组 $$$a$$$ 中的元素数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$-10^5 \le a_i \le 10^5$$$) — 初始数组 $$$a$$$。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$l_1, l_2, \dots, l_n$$$ ($$$0 \le l_i \le 1$$$),其中 $$$l_i = 0$$$ 表示位置 $$$i$$$ 已解锁,$$$l_i = 1$$$ 表示位置$$$i$$$ 已锁定。

输出

打印 $$$n$$$ 整数 - 重新排列后的数组 $$$a$$$。值$$$k$$$(最大$$$j$$$,使得$$$p_j < 0$$$(如果没有这样的$$$j$$$,则为$$$0$$$))应尽可能最小。对于每个锁定位置,打印值应等于初始值。解锁仓位上的数值应该是初始数值的排列。

如果有多个答案,则打印其中任何一个。

示例

输入 #1

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

输出 #1

1 2 3
2 -3 4 -1
-8 -6 1 4 4 7 -2
-4 0 1 6 3
-1 4 7 -8 10 -1

注意

在第一个测试用例中,您可以根据需要重新排列所有值,但任何排列都会导致 $$$k = 0$$$。例如,对于排列 $$$[1, 2, 3]$$$,$$$p=[1, 3, 6]$$$,因此不存在 $$$j$$$ 使得 $$$p_j < 0$$$。因此,$$$k = 0$$$。

在第二个测试用例中,不允许重新排列任何元素。因此,打印的数组应该与最初的数组完全相同。

在第三个测试用例中,打印数组的前缀和为 $$$p = [-8, -14, -13, -9, -5, 2, 0]$$$。最大 $$$j$$$ 为 $$$5$$$,因此 $$$k = 5$$$。不存在 $$$k < 5$$$ 的安排。

在第四个测试用例中 $$$p = [-4, -4, -3, 3, 6]$$$。

在第五个测试用例中 $$$p = [-1, 3, 10, 2, 12, 11]$$$。