← 返回题目列表

Codeforces · 1417/B

B. 两个数组

中文机器翻译题面 查看原题

RedDreamer 有一个数组 $$$a$$$,由 $$$n$$$ 个非负整数和一个不幸的整数 $$$T$$$ 组成。

让我们将长度为 $$$m$$$ 的数组 $$$b$$$ 的不幸表示为 $$$f(b)$$$ — 使得 $$$1 \le i < j \le m$$$ 且 $$$b_i + b_j = T$$$ 的整数对 $$$(i, j)$$$ 的数量。 RedDreamer 必须将 $$$a$$$ 的每个元素绘制为白色和黑色两种颜色之一(对于每个元素,颜色是独立选择的),然后创建两个数组 $$$c$$$ 和 $$$d$$$ ,以便所有白色元素属于 $$$c$$$,所有黑色元素属于 $$$d$$$(这两个数组之一有可能变为空)。 RedDreamer 希望以 $$$f(c) + f(d)$$$ 尽可能小的方式绘制元素。

例如:

- 如果 $$$n = 6$$$、$$$T = 7$$$ 且 $$$a = [1, 2, 3, 4, 5, 6]$$$,则可以将 $$$1$$$-st、$$$4$$$-th 和 $$$5$$$-th 元素绘制为白色,并将所有其他元素绘制为黑色。所以$$$c = [1, 4, 5]$$$,$$$d = [2, 3, 6]$$$,$$$f(c) + f(d) = 0 + 0 = 0$$$;
- 如果 $$$n = 3$$$、$$$T = 6$$$ 且 $$$a = [3, 3, 3]$$$,则可以将 $$$1$$$-st 元素绘制为白色,并将所有其他元素绘制为黑色。因此 $$$c = [3]$$$、$$$d = [3, 3]$$$ 和 $$$f(c) + f(d) = 0 + 1 = 1$$$。

帮助RedDreamer以最佳方式绘制阵列!

输入

第一行包含一个整数 $$$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$$$, ..., $$$a_n$$$ ($$$0 \le a_i \le 10^9$$$) — 数组的元素。

所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,打印 $$$n$$$ 整数:$$$p_1$$$、$$$p_2$$$、...、$$$p_n$$$(每个 $$$p_i$$$ 要么是 $$$0$$$ 要么 $$$1$$$)表示颜色。如果$$$p_i$$$为$$$0$$$,则$$$a_i$$$为白色,属于数组$$$c$$$,否则为黑色,属于数组$$$d$$$。

如果有多个答案可以最小化 $$$f(c) + f(d)$$$ 的值,请打印其中任何一个。

示例

输入 #1

2
6 7
1 2 3 4 5 6
3 6
3 3 3

输出 #1

1 0 0 1 1 0 
1 0 0