Two Arrays (Codeforces 1417B)
Tags: Greedy, sortings

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!

Input: 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$$$.

Output: 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.


Sample Inputs:
2
6 7
1 2 3 4 5 6
3 6
3 3 3

Sample Outputs:
1 0 0 1 1 0 
1 0 0

Solution (Python):
import sys
import math
input = sys.stdin.readline

def algo(arr, n, k):
    mid = k // 2
    c = arr.count(mid) // 2
    res = []
    if k % 2 != 0 or c == 0:
        for i in arr:
            if i <= mid:
                res.append('0')
            else:
                res.append('1')
        return ' '.join(res)
    else:
        count = 0
        for i in arr:
            if i == mid:
                count += 1
                if count <= c:
                    res.append('0')
                else:
                    res.append('1')
            elif i < mid:
                res.append('0')
            else:
                res.append('1')
        return ' '.join(res)
for _ in range(int(input())):
    (n, k) = map(int, input().split())
    arr = list(map(int, input().split()))
    res = algo(arr, n, k)
    print(res)

Solution (Python):
""""""

def solve():
    (n, t) = map(int, input().split())
    arr = list(map(int, input().split()))
    ans = [-1 for i in range(n)]
    for i in range(n):
        if arr[i] > t / 2:
            ans[i] = 0
        elif arr[i] < t / 2:
            ans[i] = 1
    color = 0
    for i in range(n):
        if ans[i] == -1:
            ans[i] = color
            color = (color + 1) % 2
    print(*ans)

def main():
    t = int(input())
    for _ in range(t):
        solve()
main()

Solution (Python):
from collections import defaultdict

def solve():
    (n, t) = [int(i) for i in input().split()]
    a = [int(i) for i in input().split()]
    count0 = defaultdict(int)
    count1 = defaultdict(int)
    l = [-1 for _ in range(n)]
    for i in range(n):
        if count0[t - a[i]] < count1[t - a[i]]:
            l[i] = 0
            count0[a[i]] += 1
        else:
            l[i] = 1
            count1[a[i]] += 1
    s = str(l[0])
    for i in range(1, n):
        s += ' '
        s += str(l[i])
    print(s)
for _ in range(int(input())):
    solve()