United We Stand (Codeforces 1859A)
Tags: Math, number theory

Given an array $$$a$$$ of length $$$n$$$, containing integers. And there are two initially empty arrays $$$b$$$ and $$$c$$$. You need to add each element of array $$$a$$$ to exactly one of the arrays $$$b$$$ or $$$c$$$, in order to satisfy the following conditions:  Both arrays $$$b$$$ and $$$c$$$ are non-empty. More formally, let $$$l_b$$$ be the length of array $$$b$$$, and $$$l_c$$$ be the length of array $$$c$$$. Then $$$l_b, l_c \ge 1$$$.  For any two indices $$$i$$$ and $$$j$$$ ($$$1 \le i \le l_b, 1 \le j \le l_c$$$), $$$c_j$$$ is not a divisor of $$$b_i$$$. Output the arrays $$$b$$$ and $$$c$$$ that can be obtained, or output $$$-1$$$ if they do not exist.

Input: Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 100$$$) — the length of array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of array $$$a$$$.

Output: For each test case, output a single integer $$$-1$$$ if a solution does not exist.Otherwise, in the first line, output two integers $$$l_b$$$ and $$$l_c$$$ — the lengths of arrays $$$b$$$ and $$$c$$$ respectively.In the second line, output $$$l_b$$$ integers $$$b_1, b_2, \ldots, b_{l_b}$$$ — the elements of array $$$b$$$.In the third line, output $$$l_c$$$ integers $$$c_1, c_2, \ldots, c_{l_c}$$$ — the elements of array $$$c$$$.If there are multiple solutions, output any of them. You can output the elements of the arrays in any order.

Note: In the first test case, a solution does not exist.In the second test case, we can obtain $$$b = [1, 3, 5]$$$ and $$$c = [2, 4]$$$. Then elements $$$2$$$ and $$$4$$$ do not divide elements $$$1, 3$$$ and $$$5$$$.In the fifth test case, we can obtain $$$b = [4, 8, 4]$$$ and $$$c = [12, 12]$$$.

Sample Inputs:
5
3
2 2 2
5
1 2 3 4 5
3
1 3 5
7
1 7 7 2 9 1 4
5
4 8 12 12 4

Sample Outputs:
-1
3 2
1 3 5 
2 4 
1 2
1 
3 5 
2 5
1 1 
2 4 7 7 9 
3 2
4 8 4 
12 12

Solution (Python):
cases = int(input())
for case in range(cases):
    input()
    arr = list(map(int, input().split()))
    if arr.count(arr[0]) == len(arr):
        print(-1)
    else:
        _max = max(arr)
        c = [_max] * arr.count(_max)
        b = [i for i in arr if i != _max]
        print(len(b), len(c))
        print(' '.join(map(str, b)))
        print(' '.join(map(str, c)))

Solution (Python):
def solve():
    n = int(input())
    inp = list(map(int, input().split()))
    inp.sort()
    if inp[-1] == inp[0]:
        print('-1')
        return
    else:
        it = 0
        while inp[it] == inp[0]:
            it += 1
        print(f'{it} {n - it}')
        print(' '.join(map(str, inp[:it])))
        print(' '.join(map(str, inp[it:])))

def main():
    t = int(input())
    for _ in range(t):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
def solve(n, nums):
    (numsB, numsC) = ([], [])
    nums.sort()
    for i in range(n):
        numsB.append(nums[i])
        for j in range(i + 1, n):
            if nums[i] == nums[j]:
                break
            if nums[i] % nums[j] != 0:
                numsC.extend(nums[j:])
                return f"{len(numsB)} {len(numsC)}\n{' '.join(map(str, numsB))}\n{' '.join(map(str, numsC))}"
    return -1
T = int(input())
for t in range(T):
    n = int(input())
    nums = list(map(int, input().split()))
    print(solve(n, nums))