Two Arrays

题意翻译

- 给出一个序列，和一个常数 $T$，将序列中元素分到两个集合里（集合可为空），使得两个集合内部 满足 $i\lt j$ 且 $a_i+a_j=T$ 的二元组 $(i,j)$ 数量 的和最小，输出方案（不需要输出总数；两个集合分别用 0 和 1 表示）。 - 数据组数 $t\le1000$，序列长度 $n\le10^5$，常数 $0\le T\le10^9$，元素大小 $0\le a_i\le10^9$。

题目描述

RedDreamer has an array $ a $ consisting of $ n $ non-negative integers, and an unlucky integer $ T $ . Let's denote the misfortune of array $ b $ having length $ m $ as $ f(b) $ — the number of pairs of integers $ (i, j) $ such that $ 1 \le i < j \le m $ and $ b_i + b_j = T $ . RedDreamer has to paint each element of $ a $ into one of two colors, white and black (for each element, the color is chosen independently), and then create two arrays $ c $ and $ d $ so that all white elements belong to $ c $ , and all black elements belong to $ d $ (it is possible that one of these two arrays becomes empty). RedDreamer wants to paint the elements in such a way that $ f(c) + f(d) $ is minimum possible. For example: - if $ n = 6 $ , $ T = 7 $ and $ a = [1, 2, 3, 4, 5, 6] $ , it is possible to paint the $ 1 $ -st, the $ 4 $ -th and the $ 5 $ -th elements white, and all other elements black. So $ c = [1, 4, 5] $ , $ d = [2, 3, 6] $ , and $ f(c) + f(d) = 0 + 0 = 0 $ ; - if $ n = 3 $ , $ T = 6 $ and $ a = [3, 3, 3] $ , it is possible to paint the $ 1 $ -st element white, and all other elements black. So $ c = [3] $ , $ d = [3, 3] $ , and $ f(c) + f(d) = 0 + 1 = 1 $ . Help RedDreamer to paint the array optimally!

输入输出格式

输入格式

The first line contains one integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. Then $ t $ test cases follow. The first line of each test case contains two integers $ n $ and $ T $ ( $ 1 \le n \le 10^5 $ , $ 0 \le T \le 10^9 $ ) — the number of elements in the array and the unlucky integer, respectively. The second line contains $ n $ integers $ a_1 $ , $ a_2 $ , ..., $ a_n $ ( $ 0 \le a_i \le 10^9 $ ) — the elements of the array. The sum of $ n $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case print $ n $ integers: $ p_1 $ , $ p_2 $ , ..., $ p_n $ (each $ p_i $ is either $ 0 $ or $ 1 $ ) denoting the colors. If $ p_i $ is $ 0 $ , then $ a_i $ is white and belongs to the array $ c $ , otherwise it is black and belongs to the array $ d $ . If there are multiple answers that minimize the value of $ f(c) + f(d) $ , print any of them.

输入输出样例

输入样例 #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