You are given an array $A$ with size $N$. You can rearrange $A$ in any order. Then, seperate the array $A$ into $K$ continuous subarrays. You can freely choose the points of seperation, but each subarray must have positive size.
For a subarray, its $score$ is defined as follows:
- Let the size of the array be $x$ and the subarray be $B_1, B_2, ...\ , B_x$ Then, $score=B_1 \times B_2 \times ... \times B_x$.
Your final score is the sum of scores of all subarrays.
You task is simple: Maximize the final score. Note that you are not required to output the maximal final score. Instead, output the $K$ subarrays that you formed which achieves maximal score.
Input
The first line contains two integers $N$ and $K$.
The second line contains $N$ integers $A_1, A_2, ...\ , A_N$.
Output
Output $K$ lines.
For the $i^{th}$ line, output a single integer $X_i$ at the start of the $i^{th}$ line, denoting the size of the $i^{th}$ subarray you formed, followed by $X_i$ integers, denoting the $i^{th}$ subarray.
If there are multiple answers, any of them will be accepted.
Subtasks
For all test cases:
- $1 \le K \le N \le 2 \times 10^5$
- $0 \le A_i \le 10^6$
| Subtask | Score | Additional Constraints |
|---|---|---|
| $1$ | $6$ | $K = 1$ |
| $2$ | $7$ | $K = N$ |
| $3$ | $15$ |
$N = 3$ $K = 2$ |
| $4$ | $11$ | $A_i = 1$ for $1 \le i \le N$ |
| $5$ | $19$ | $A_i \ge 2$ for $1 \le i \le N$ |
| $6$ | $18$ | $A_i \neq 1$ for $1 \le i \le N$ |
| $7$ | $24$ | No Additional Constraints |
Sample Test Cases
| Input | Output | |
|---|---|---|
| 4 2 9 0 3 0 |
2 3 9 2 0 0 |
|
We can reorder $A$ to $[9, 3, 0, 0]$. Then, seperate $A$ into $K=2$ continuous subarrays $[A_1, A_2]$ and $[A_3, A_4]$. The score of the first subarray is $A_1 \times A_2=9 \times 3 = 27$. The score of the second subarray is $A_3 \times A_4 = 0 \times 0 = 0$. The total score is $27+0=27$. It can be shown that $27$ is the maximal score. Remember that you do not need to output the maximal score. You just need to output the $2$ subarrays that you formed. |
||
| 5 3 2 0 2 1 1 |
1 0 2 2 2 2 1 1 |
|
Note that the order of the subarrays that you output does not matter. |
||
Scoring: Per Subtask
Authored by s22f26
Appeared in 2026 Mini Comp 5 (Pre-HKSC)