QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 2048 MB Total points: 100

#10346. Make Triangle

统计

给定 $n$ 个正整数 $x_1, x_2, \dots, x_n$ 以及三个正整数 $n_a, n_b, n_c$,满足 $n_a + n_b + n_c = n$。

你需要将这 $n$ 个正整数分成三组,使得:

  • 第一组包含 $n_a$ 个数,第二组包含 $n_b$ 个数,第三组包含 $n_c$ 个数。
  • 设 $s_a$ 为第一组中数字的和,$s_b$ 为第二组中数字的和,$s_c$ 为第三组中数字的和。那么 $s_a, s_b, s_c$ 必须能够构成一个面积为正的三角形的三条边。

判断这是否可行。如果可行,请给出一个具体的划分方案。

输入格式

每个测试点包含多个测试用例。第一行包含一个整数 $t$ ($1 \le t \le 100\,000$),表示测试用例的数量。接下来是 $t$ 个测试用例的描述。

每个测试用例的第一行包含整数 $n, n_a, n_b, n_c$ ($3 \le n \le 200\,000$, $1 \le n_a, n_b, n_c \le n - 2$, $n_a + n_b + n_c = n$),分别表示要划分的整数个数以及三个组的目标大小。

每个测试用例的第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$ ($1 \le x_i \le 10^9$)。

保证所有测试用例中 $n$ 的总和不超过 $200\,000$。

输出格式

对于每个测试用例,如果可以将数字划分为满足所有条件的三个组,则输出 YES。否则,输出 NO。

如果存在这样的划分,请按以下方式描述这三个组:

在下一行输出 $n_a$ 个整数 $a_1, a_2, \dots, a_{n_a}$,表示第一组中的数字。 在下一行输出 $n_b$ 个整数 $b_1, b_2, \dots, b_{n_b}$,表示第二组中的数字。 在下一行输出 $n_c$ 个整数 $c_1, c_2, \dots, c_{n_c}$,表示第三组中的数字。

这 $n_a + n_b + n_c = n$ 个整数应当是 $x_1, x_2, \dots, x_n$ 的一个排列,并且满足题目描述中的条件。

如果存在多种解,输出其中任意一种即可。

样例

输入 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

说明

在第一个测试用例中,我们可以将两个 1 放入每一组:每组的和均为 2,而边长为 2, 2, 2 可以构成一个面积为正的三角形。

在第二个和第三个测试用例中,可以证明不存在这样的分组方式。

在第四个测试用例中,我们可以将数字 16 放入第一组(和为 16),将数字 12 和 1 放入第二组(和为 13),将剩余的五个 1 放入第三组(和为 5),因为边长为 16, 13, 5 可以构成一个面积为正的三角形。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.