CF1417B Two Arrays

RedDreamer 有一个由 $n$ 个非负整数组成的数组 $a$，以及一个不吉利的整数 $T$。 我们定义长度为 $m$ 的数组 $b$ 的“不幸值” $f(b)$ 为满足 $1 \le i < j \le m$ 且 $b_i + b_j = T$ 的整数对 $(i, j)$ 的数量。RedDreamer 需要将数组 $a$ 的每个元素独立地染成白色或黑色，然后分别构造两个数组 $c$ 和 $d$，使所有白色元素属于 $c$，所有黑色元素属于 $d$（允许 $c$ 或 $d$ 为空）。RedDreamer 希望通过合理染色，使 $f(c) + f(d)$ 的值尽可能小。 例如： - 如果 $n = 6$，$T = 7$，$a = [1, 2, 3, 4, 5, 6]$，可以将第 $1$、$4$、$5$ 个元素染成白色，其余元素染成黑色。此时 $c = [1, 4, 5]$，$d = [2, 3, 6]$，$f(c) + f(d) = 0 + 0 = 0$。 - 如果 $n = 3$，$T = 6$，$a = [3, 3, 3]$，可以将第 $1$ 个元素染成白色，其余元素染成黑色。此时 $c = [3]$，$d = [3, 3]$，$f(c) + f(d) = 0 + 1 = 1$。 请你帮助 RedDreamer 合理染色，使 $f(c) + f(d)$ 最小。

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例数量。接下来有 $t$ 组测试数据。 每组测试数据的第一行包含两个整数 $n$ 和 $T$（$1 \le n \le 10^5$，$0 \le T \le 10^9$），分别表示数组的长度和不吉利的整数。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^9$），表示数组的元素。 所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出 $n$ 个整数 $p_1, p_2, \ldots, p_n$（每个 $p_i$ 为 $0$ 或 $1$），表示每个元素的颜色。如果 $p_i = 0$，则 $a_i$ 染成白色，属于数组 $c$；如果 $p_i = 1$，则 $a_i$ 染成黑色，属于数组 $d$。 如果有多种方案都能使 $f(c) + f(d)$ 最小，输出任意一种即可。

由 ChatGPT 4.1 翻译