P16372 [IATI 2026] Partition

为了保证本题可以正常评测，本题时间限制为 8 秒。但是，本题的交互库需要大约 900 毫秒的运行时间，如果你的代码运行时间（算上交互库）超过 1.2 秒，你的代码将被视作 TLE。 滥用本题评测资源将被封号。

人们常说兄弟姐妹之间倾向于尽可能公平地分享东西。这里，我们考虑一个关于两姐妹——Martina 和 **D**eni——的有些有趣的情形。Martina 最近买了 $N$ 包糖果，其中第 $i$ 包（$0 \le i \le N-1$）包含正整数颗糖果 $A_i$，糖果总数为 $S = A_0 + A_1 + \dots + A_{N-1}$。姐妹俩需要将糖果分给彼此。对于她们而言，糖果的数量并不是唯一重要的事情，包裹的数量同样重要！经过多番争论，姐妹俩就以下流程达成了一致。 首先，**D**eni 可以按她喜欢的任何方式排列这些糖果包。形式化地，她将给出这些糖果包的一个排列。我们用下标序列 $i_0, i_1, \dots, i_{N-1}$ 表示这个排列，其中 $\{i_0, i_1, \dots, i_{N-1}\} = \{0, 1, \dots, N-1\}$。然后 Martina 按顺序将 $A_{i_0}, A_{i_1}, \dots$ 这些糖果包依次递给 **D**eni，直至给出的糖果总数达到 $\ge \frac{S}{2}$。此后，Martina 将剩余的糖果包留给自己，此时糖果包就完全在两人之间分配完毕。 **D**eni 深爱她的妹妹，因此她会试图最小化她得到的包裹数与妹妹得到的包裹数之差的绝对值。所以，她希望在所有可能的排列中选出一个能够最小化该差值的排列。编写一个程序 **partition**，在 $T$ 个场景下帮助她确定这样的一个糖果包排列。如果存在多组解，你只需返回其中任意一组。 ### 实现细节 你需要实现如下函数 $\texttt{solve}$： ```cpp std::vector solve(std::vector A) ``` - $A$：包含 $N$ 个正整数的向量，表示 Martina 所买糖果包中的糖果数量。 该函数在一个测试数据中会被调用 $T$ 次——每个场景调用一次。对于每个场景，它需要返回一个向量，其中包含下标 $0, 1, \dots, N-1$ 的一个排列，使得基于该排列所得分配结果的包裹数之差的绝对值被最小化。

输入格式： - 第 $1$ 行：一个正整数 $T$ —— 场景的数量； - 第 $2 + 2 \times j$ 行：一个正整数 $N$ —— 第 $j$ 个场景中糖果包的数量； - 第 $3 + 2 \times j$ 行：$A_0 \ A_1 \ \dots \ A_{N-1}$ —— 第 $j$ 个场景中各糖果包内的糖果数量。

输出格式： - 第 $j$ 行：对应第 $j$ 次调用 $\texttt{solve}$ 所返回的数字。

### 样例 1 解释 所给的第一个样例输出是众多可能解中的一个。重排后糖果包内的糖果数量依次为：$5, 3, 4, 4, 1, 3, 6, 6, 1$。**D**eni 将得到下标为 $0, 3, 6, 7, 4$ 的糖果包，从而获得 $5 + 3 + 4 + 4 + 1 = 17$ 颗糖果。注意 $5 + 3 + 4 + 4 = 16 < \frac{S}{2} = 16.5$，因此 Martina 无法更早停止。Martina 将取走剩余的糖果包，因此分配中包裹数之差的绝对值为 $\lvert 5 - 4 \rvert = 1$。可以证明这对于该测试数据是最优的。 ### 数据范围 - $1 \le N \le 2 \times 10^6$ - $1 \le \sum N \le 10^7$，其中 $\sum N$ 是该测试数据所有场景下 $N$ 的总和。 - $1 \le T \le 5 \times 10^3$ - 对于所有 $0 \le i \le N-1$，有 $1 \le A_i \le 10^9$ ### 子任务 | **子任务** | **分数** | **依赖子任务** | **$N$** | **$\sum N$** | **其他限制** | | :---: | :---: | :---: | :---: | :---: | :---: | | $0$ | $0$ | $-$ | $-$ | $-$ | 样例测试。 | | $1$ | $3$ | $-$ | $\le 10^5$ | $\le 10^5$ | 所有值 $A_0, A_1, \dots, A_{N-1}$ 均出现偶数次；对于 $0 \le i \le N-1$ 有 $A_i \le 3 \times 10^7$；$T = 1$ | | $2$ | $3$ | $-$ | $\le 25$ | $\le 250$ | 对于 $0 \le i \le N-1$ 有 $A_i = 2^i$ | | $3$ | $3$ | $2$ | $\le 10^6$ | $\le 5 \times 10^6$ | 对于 $0 \le i \le N-1$ 有 $A_i = 2^{s_i}$，其中 $0 \le s_i \le 25$ | | $4$ | $5$ | $-$ | $\le 2 \times 10^6$ | $\le 10^7$ | 对于 $0 \le i \le N-1$ 有 $A_i = i+1$ | | $5$ | $4$ | $-$ | $\le 7$ | $\le 3.5 \times 10^4$ | $-$ | | $6$ | $6$ | $0$ | $\le 20$ | $\le 200$ | ^ | | $7$ | $19$ | $0, 2, 6$ | $\le 2 \times 10^3$ | $\le 10^4$ | ^ | | $8$ | $28$ | $0-2, 5-7$ | $\le 10^5$ | $\le 5 \times 10^5$ | ^ | | $9$ | $29$ | $0-7$ | $\le 2 \times 10^6$ | $\le 10^7$ | ^ | 一个子任务的分数仅当该子任务及其所依赖子任务的全部测试数据均成功通过时才能获得。 翻译由 DeepSeek V4 Pro 完成