codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```