P16456 [UOI 2026] Intersection of Prefix Sums

给定一个包含 $n$ 个整数的数组 $a$ 和一个整数 $x$。 你需要重新排列数组中的元素，使得在得到的数组中，没有任何一个 **非空** 前缀的和等于 $x$，或者报告这是不可能的。 换句话说，你需要找出数组 $a$ 的一个排列 $p_1, p_2, \dots, p_n$，使得对于每个 $k$ $(1 \le k \le n)$，都满足 $p_1 + p_2 + \dots + p_k \neq x$。

第一行包含一个整数 $t$ $(1 \le t \le 10^4)$ —— 测试数据的组数。 每组测试数据由两行组成。 每组数据的第一行包含两个整数 $n$ 和 $x$ $(1 \le n \le 10^5, |x| \le 10^{15})$ —— 数组的元素个数以及被禁止的前缀和。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(|a_i| \le 10^9)$ —— 数组中的元素。 保证所有测试数据的 $n$ 之和不超过 $10^5$。

对于每组测试数据，按以下格式输出答案。 第一行，如果存在数组 $a$ 的一个排列满足没有非空前缀的和等于 $x$，则输出 `YES`。否则输出 `NO`。 如果答案为 `YES`，则在第二行输出 $n$ 个由空格分隔的整数——数组 $a$ 的一个符合要求的排列。 如果存在多个正确的排列，你可以输出其中任意一个。 字符串 `YES` 和 `NO` 的大小写不限。例如，`yes`、`Yes` 和 `YES` 均被视为相同。 对于每个子任务，如果你对其中的所有测试用例都能正确判断是否存在所需排列，即能正确输出 `YES` 或 `NO`，就可以获得 **一半的分数**。也就是说，要获得一半分数，只需对相应子任务的每个测试用例正确地输出 `YES` 或 `NO` 即可。 注意，如果你输出了 `YES`，则下一行必须恰好包含 $n$ 个由空格分隔的整数。要获得 **满分**，这些整数必须构成数组 $a$ 的一个排列，且不存在和为 $x$ 的非空前缀。 若只要求 **一半** 的分数，则这些 $n$ 个整数可以是任意整数，甚至可以不是数组 $a$ 中的元素。 如果输出 `YES` 后没有接着输出恰好 $n$ 个整数，那么即使是一半分数也无法获得。 例如，假设在某个测试用例中 $n = 5$ 且正确答案为 `YES`。那么要获得一半分数，你可以输出： ``` YES 1 1 1 1 1 ``` 即使数组 $a$ 中根本不包含这些数。 但是你不能只输出： ``` YES ``` 这样的话，在 `YES` 之后并没有输出恰好 $n$ 个处于 $[-10^9, 10^9]$ 范围内的整数。

在第一个样例中，存在一个排列 $[2, 1, 2, 1, -3, 2]$。该序列的前缀和为 $[2, 3, 5, 6, 3, 5]$，并不包含数字 $4$。其他排列也有效。 在第二个样例中，只有一个排列，其前缀和中会包含数字 $7$。 ### 计分 - （$2$ 分）：对于所有 $i$，满足 $a_i = a_1$； - （$4$ 分）：$x = 0$； - （$4$ 分）：$t = 1$，$n \le 9$； - （$6$ 分）：$t = 1$，$n \le 15$； - （$8$ 分）：对于所有 $i$ 有 $a_i > 0$，且 $x \le 200$； - （$14$ 分）：数组中至多只有两个不同的值； - （$10$ 分）：如果存在正确排列，那么只需将数组的第一个元素与另一个元素交换即可得到； - （$12$ 分）：对于所有 $i$ 有 $a_i > 0$； - （$16$ 分）：数组中恰好有一个负数； - （$24$ 分）：无额外限制。 翻译由 DeepSeek V4 Pro 完成