Make Triangle

题面翻译

题目描述

已知 $n$ 个数 $\{x_i\}$，求任意一种把它们分成数量分别为 $n_a, n_b, n_c$ （保证其和为 $n$）的 $3$ 份的方案，满足各份中的数的和 $s_a, s_b, s_c$ 可以构成三角形的三边（不允许三个顶点共线）。

输入格式

一行 $t$ 表示数据组数；接着每组数据中：

• 第 1 行：$n, n_a, n_b, n_c$
• 第 2 行：$x_1, x_2, \dots, x_n$

$t\leq 10^5,\quad \sum n\leq 2\times 10^5, \quad n_a, n_b, n_c\geq 1,\quad x_i \leq 10^9$

输出格式

对每组数据，如果不存在方案，输出 $\texttt{NO}$；否则输出一行 $\texttt{YES}$ 以及：

• 下一行：分在一组内的 $n_a$ 个整数；
• 下一行：分在一组内的 $n_b$ 个整数；
• 下一行：分在一组内的 $n_c$ 个整数。

题目描述

You are given $n$ positive integers $x_1, x_2, \ldots, x_n$ and three positive integers $n_a, n_b, n_c$ satisfying $n_a+n_b+n_c = n$ .

You want to split the $n$ positive integers into three groups, so that:

• The first group contains $n_a$ numbers, the second group contains $n_b$ numbers, the third group contains $n_c$ numbers.
• Let $s_a$ be the sum of the numbers in the first group, $s_b$ be the sum in the second group, and $s_c$ be the sum in the third group. Then $s_a, s_b, s_c$ are the sides of a triangle with positive area.

Determine if this is possible. If this is possible, find one way to do so.

输入格式

Each test contains multiple test cases. The first line contains an integer $t$ ( $1\le t\le 100\,000$ ) — the number of test cases. The descriptions of the $t$ test cases follow.

The first line of each test case contains the integers $n, n_a, n_b, n_c$ ( $ 3 \leq n \leq 200\,000, 1\leq n_a,n_b,n_c \leq n-2, n_a+n_b+n_c = n $ ) — the number of integers to split into three groups, and the desired sizes of the three groups.

The second line of each test case contains $n$ integers $x_1, x_2, \ldots, x_n$ ( $1 \leq x_i \leq 10^{9}$ ).

It is guaranteed that the sum of $n$ over all test cases does not exceed $200\,000$ .

输出格式

For each test case, print $\texttt{YES}$ if it is possible to split the numbers into three groups satisfying all the conditions. Otherwise, print $\texttt{NO}$ .

If such a split exists, then describe the three groups as follows.

On the next line, print $n_a$ integers $a_1, a_2, \ldots, a_{n_a}$ — the numbers in the first group.

On the next line, print $n_b$ integers $b_1, b_2, \ldots, b_{n_b}$ — the numbers in the second group.

On the next line, print $n_c$ integers $c_1, c_2, \ldots, c_{n_c}$ — the numbers in the third group.

These $n_a+n_b+n_c=n$ integers should be a permutation of $x_1, x_2, \ldots, x_n$ , and they should satisfy the conditions from the statement.

If there are multiple solutions, print any of them.

样例 #1

样例输入 #1

4
6 2 2 2
1 1 1 1 1 1
5 3 1 1
1 1 1 1 1
6 2 2 2
1 1 1 1 1 3
8 1 2 5
16 1 1 1 1 1 1 12

样例输出 #1

YES
1 1 
1 1 
1 1 
NO
NO
YES
16 
12 1 
1 1 1 1 1

提示

In the first test case, we can put two $1$ s into each group: the sum in each group would be $2$ , and there exists a triangle with positive area and sides $2$ , $2$ , $2$ .

In the second and third test cases, it can be shown that there is no such way to split numbers into groups.

In the fourth test case, we can put number $16$ into the first group, with sum $16$ , numbers $12$ and $1$ into the second group, with sum $13$ , and the remaining five $1$ s into the third group, with sum $5$ , as there exists a triangle with positive area and sides $16, 13, 5$ .