P16372 [IATI 2026] Partition

It is often said that siblings tend to share things as equally as possible. Here, we consider a somewhat interesting situation involving two sisters -- Martina and $\textbf{D}$eni. Martina has recently bought $N$ packs of candies, where the $i$-th packs contains a positive number of candies $A_i$ for $0 \le i \le N-1$ and the total number of candies is $S = A_0 + A_1 + \dots + A_{N-1}$. The sisters need to divide the candies between each other. For them, the number of candies is not the only important thing, but also the number of packs! After many arguments, the sisters have agreed on the following procedure. First, $\textbf{D}$eni will order the packs in any way she wants. Formally, she will produce a permutation of them. Let us denote this permutation by indices $i_0, i_1, \dots, i_{N-1}$, where $\{i_0, i_1, \dots, i_{N-1}\} = \{0, 1, \dots, N-1\}$. Then Martina gives the packs $A_{i_0}, A_{i_1}, \dots$ to \textbf{D}eni in that order until the total number of candies given becomes $\ge \frac{S}{2}$. After that, Martina takes the remaining packs for herself and then the packs are fully partitioned between them. $\textbf{D}$eni loves her sister and so she will try to minimize the absolute difference between the number of packs she receives and the number of packs her sister receives. Therefore, she wants to pick a permutation that minimizes this among all possible permutations of the packs. Write a program $\textbf{partition}$ that will help her determine such a permutation of the packs of candies in $T$ scenarios. If there are multiple solutions, you should return any one of them. ### Implementation details You should implement a function $\texttt{solve}$: ```cpp std::vector solve(std::vector A) ``` - $A$: vector of $N$ positive numbers, representing the number of candies in the packs bought by Martina. This function is called $T$ times -- once for each scenario in а test case. For each scenario, it has to return a vector containing a permutation of the indices $0, 1, \dots, N-1$ such that it minimizes the absolute difference between the number of packs in the resulting partition from the permutation.

Input format: - line $1$: one positive number $T$ -- the number of scenarios; - line $2 + 2 \times j$: one positive number $N$ -- the number of packs in the $j$-th scenario; - line $3 + 2 \times j$: $A_0 \ A_1 \ \dots \ A_{N-1}$ -- the number of candies in the packs in the $j$-th scenario.

Output format: - line $j$: the numbers returned by the $j$-th call to $\texttt{solve}$.

### Sample 1 Explanation The given output of the first sample is one of multiple possible solutions. The number of candies in the reordered packs are: $5, 3, 4, 4, 1, 3, 6, 6, 1$. $\textbf{D}$eni will receive the packs with indices $0, 3, 6, 7, 4$, thus getting $5 + 3 + 4 + 4 + 1 = 17$ candies. Note that $5 + 3 + 4 + 4 = 16 < \frac{S}{2} = 16.5$, so Martina can't stop earlier. Martina will take the remaining packs so the absolute difference between the number of packs in the partition is $\lvert 5 - 4 \rvert = 1$. It can be proven that this is optimal for the test. ### Constraints - $1 \le N \le 2 \times 10^6$ - $1 \le \sum N \le 10^7$ where $\sum N$ is the sum of all $N$ among the scenarios in a given test case. - $1 \le T \le 5 \times 10^3$ - $1 \le A_i \le 10^9$ for all $0 \le i \le N-1$ ### Subtasks | **Subtask** | **Points** | **Required
subtasks** | **$N$** | **$\Sigma N$** | **Other constraints** | | :---: | :---: | :---: | :---: | :---: | :---: | | $0$ | $0$ | $-$ | $-$ | $-$ | The sample test. | | $1$ | $3$ | $-$ | $\le 10^5$ | $\le 10^5$ | All values $A_0, A_1, \dots, A_{N-1}$ appear an even number of times; $A_i \le 3 \times 10^7$ for $0 \le i \le N-1$; $T = 1$ | | $2$ | $3$ | $-$ | $\le 25$ | $\le 250$ | $A_i = 2^i$ for $0 \le i \le N-1$ | | $3$ | $3$ | $2$ | $\le 10^6$ | $\le 5 \times 10^6$ | $A_i = 2^{s_i}$ for $0 \le i \le N-1$, where $0 \le s_i \le 25$ | | $4$ | $5$ | $-$ | $\le 2 \times 10^6$ | $\le 10^7$ | $A_i = i+1$ for $0 \le i \le N-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$ | ^ | The points for a given subtask are obtained only if all the tests for it and the required subtasks are successfully passed.