← 返回题目列表

Codeforces · 2222/D

D. 排列构造

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

Kirara Magic & PIKASONIC - 芙罗拉

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

对于倒置$$$^{\text{*}}$$$ $$$(i,j)$$$ 排列$$$^{\text{†}}$$$ $$$p$$$,其 值 定义为 $$$\sum\limits_{k=i}^{j-1} a_k$$$。的 排列的 美女 是 值 超过所有的倒置。

你必须构造一个长度为 $$$n$$$ 的排列 $$$p$$$ ,使其最大化 美女.

$$$^{\text{*}}$$$长度$$$n$$$的排列$$$p$$$中的反转是一对索引$$$(i,j)$$$,使得$$$1\leq i \lt j\leq n$$$和$$$p_i \gt p_j$$$。例如,当 $$$p=[1,4,2,3,5]$$$ 时,$$$(2,3)$$$ 是反转对,但 $$$(1,2)$$$ 不是反转($$$p_1=1$$$ 不大于 $$$p_2=4$$$),并且 $$$(4,2)$$$ 也不是反转(索引 $$$4$$$ 是不少于$$$2$$$)。当 $$$p=[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$$$ ($$$1\le n \le 2\cdot 10^5$$$) — $$$a$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9\leq a_i\leq 10^9$$$) — $$$a$$$ 的元素。

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

输出

对于每个测试用例,打印一行包含 $$$n$$$ 整数 — 最大化其值的排列 $$$p$$$ 美女.

如果有多个有效答案,您可以打印其中任何一个。

示例

输入
复制

7
1
0
2
1000000000 -1000000000
3
1 2 3
4
-1 -2 -3 -4
5
-1 2 -3 2 -1
6
1 -1 3 -4 1 -3
7
-3 -2 -1 4 -1 -2 -3

输出
复制

1
2 1
3 2 1
1 2 3 4
3 4 1 5 2
5 2 4 1 6 3
1 4 6 7 2 3 5

注意

在第一个测试用例中,排列 $$$p$$$ 只能是 $$$[1]$$$。

在第二个测试用例中,对于排列 $$$p=[2,1]$$$,唯一的反转是 $$$(1,2)$$$,其 值 是 $$$10^9$$$,所以 美女 的排列是 $$$10^9$$$。可以证明不存在更大的排列 美女.

在第三个测试用例中,对于排列 $$$p=[3,2,1]$$$,所有反转都是 $$$(1,2)$$$、$$$(1,3)$$$ 和 $$$(2,3)$$$,其中 值 分别为 $$$1$$$、$$$3$$$ 和 $$$2$$$,因此 美女 的排列是$$$1+3+2=6$$$。可以证明不存在更大的排列 美女.

在第四个测试用例中,对于排列 $$$p=[1,2,3,4]$$$,没有反转,因此 排列的 美女 是 $$$0$$$。可以证明不存在更大的排列 美女.

在第五个测试用例中,对于排列 $$$p=[3,4,1,5,2]$$$,其 美女 是 $$$6$$$。