Ternary XOR (Codeforces 1328C)
Tags: Greedy, implementation

A number is ternary if it contains only digits $$$0$$$, $$$1$$$ and $$$2$$$. For example, the following numbers are ternary: $$$1022$$$, $$$11$$$, $$$21$$$, $$$2002$$$.You are given a long ternary number $$$x$$$. The first (leftmost) digit of $$$x$$$ is guaranteed to be $$$2$$$, the other digits of $$$x$$$ can be $$$0$$$, $$$1$$$ or $$$2$$$.Let's define the ternary XOR operation $$$\odot$$$ of two ternary numbers $$$a$$$ and $$$b$$$ (both of length $$$n$$$) as a number $$$c = a \odot b$$$ of length $$$n$$$, where $$$c_i = (a_i + b_i) \% 3$$$ (where $$$\%$$$ is modulo operation). In other words, add the corresponding digits and take the remainders of the sums when divided by $$$3$$$. For example, $$$10222 \odot 11021 = 21210$$$.Your task is to find such ternary numbers $$$a$$$ and $$$b$$$ both of length $$$n$$$ and both without leading zeros that $$$a \odot b = x$$$ and $$$max(a, b)$$$ is the minimum possible.You have to answer $$$t$$$ independent test cases.

Input: The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow. The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^4$$$) — the length of $$$x$$$. The second line of the test case contains ternary number $$$x$$$ consisting of $$$n$$$ digits $$$0, 1$$$ or $$$2$$$. It is guaranteed that the first digit of $$$x$$$ is $$$2$$$. It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^4$$$ ($$$\sum n \le 5 \cdot 10^4$$$).

Output: For each test case, print the answer — two ternary integers $$$a$$$ and $$$b$$$ both of length $$$n$$$ and both without leading zeros such that $$$a \odot b = x$$$ and $$$max(a, b)$$$ is the minimum possible. If there are several answers, you can print any.


Sample Inputs:
4
5
22222
5
21211
1
2
9
220222021

Sample Outputs:
11111
11111
11000
10211
1
1
110111011
110111010

Solution (Python):
for g in [*open(0)][2::2]:
    g = g.strip()
    a = g.replace('2', '1')
    if '1' in g:
        c = g.index('1')
        print(a[:c] + '1' + '0' * (len(g) - 1 - c), a[:c] + '0' + g[c + 1:])
    else:
        print(a, a)

Solution (Python):
import os
import sys
from io import BytesIO, IOBase

def main():
    T = int(input())
    for t in range(T):
        n = int(input())
        s = input()
        a = '1'
        b = '1'
        for l in range(1, n):
            if s[l] == '2':
                a += '1'
                b += '1'
            elif s[l] == '0':
                a += '0'
                b += '0'
            else:
                break
        if len(a) != n:
            a += '1'
            b += '0'
            for i in range(l + 1, n):
                if s[i] == '2':
                    a += '0'
                    b += '2'
                elif s[i] == '1':
                    a += '0'
                    b += '1'
                else:
                    a += '0'
                    b += '0'
        print(a)
        print(b)
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()

Solution (Python):
import math, os, sys, random
from math import comb
from collections import defaultdict
from fractions import Fraction
from decimal import Decimal
if os.path.exists('input.txt'):
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')
input = sys.stdin.readline

def solve():
    n = int(input())
    k = input().split()
    k = ''.join(k)
    (a, b) = ('1', '1')
    flag = False
    for i in range(1, n):
        if k[i] == '0':
            a = a + '0'
            b = b + '0'
        elif k[i] == '1':
            if flag:
                a = a + '0'
                b = b + '1'
            else:
                a = a + '1'
                b = b + '0'
                flag = True
        elif flag:
            a = a + '0'
            b = b + '2'
        else:
            a = a + '1'
            b = b + '1'
    print(a)
    print(b)
for _ in range(int(input())):
    solve()
sys.stdout.close()
sys.stdin.close()