1417B.md (2259B)
1 Source: https://codeforces.com/problemset/problem/1417/B 2 3 B. Two Arrays 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 RedDreamer has an array $a$ consisting of $n$ non-negative integers, and an unlucky integer $T$. 22 23 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 \lt 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. 24 25 For example: 26 27 * 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$; 28 * 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$. 29 30 Help RedDreamer to paint the array optimally! 31 32 Input 33 34 The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases. Then $t$ test cases follow. 35 36 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. 37 38 The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($0 \le a_i \le 10^9$) — the elements of the array. 39 40 The sum of $n$ over all test cases does not exceed $10^5$. 41 42 Output 43 44 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$. 45 46 If there are multiple answers that minimize the value of $f(c) + f(d)$, print any of them. 47 48 Example 49 50 Input 51 52 ``` 53 2 54 6 7 55 1 2 3 4 5 6 56 3 6 57 3 3 3 58 ``` 59 60 Output 61 62 ``` 63 1 0 0 1 1 0 64 1 0 0 65 ```