Pair Programming (Codeforces 1547C)
Tags: Greedy, two pointers

Monocarp and Polycarp are learning new programming techniques. Now they decided to try pair programming.It's known that they have worked together on the same file for $$$n + m$$$ minutes. Every minute exactly one of them made one change to the file. Before they started, there were already $$$k$$$ lines written in the file.Every minute exactly one of them does one of two actions: adds a new line to the end of the file or changes one of its lines.Monocarp worked in total for $$$n$$$ minutes and performed the sequence of actions $$$[a_1, a_2, \dots, a_n]$$$. If $$$a_i = 0$$$, then he adds a new line to the end of the file. If $$$a_i > 0$$$, then he changes the line with the number $$$a_i$$$. Monocarp performed actions strictly in this order: $$$a_1$$$, then $$$a_2$$$, ..., $$$a_n$$$.Polycarp worked in total for $$$m$$$ minutes and performed the sequence of actions $$$[b_1, b_2, \dots, b_m]$$$. If $$$b_j = 0$$$, then he adds a new line to the end of the file. If $$$b_j > 0$$$, then he changes the line with the number $$$b_j$$$. Polycarp performed actions strictly in this order: $$$b_1$$$, then $$$b_2$$$, ..., $$$b_m$$$.Restore their common sequence of actions of length $$$n + m$$$ such that all actions would be correct — there should be no changes to lines that do not yet exist. Keep in mind that in the common sequence Monocarp's actions should form the subsequence $$$[a_1, a_2, \dots, a_n]$$$ and Polycarp's — subsequence $$$[b_1, b_2, \dots, b_m]$$$. They can replace each other at the computer any number of times.Let's look at an example. Suppose $$$k = 3$$$. Monocarp first changed the line with the number $$$2$$$ and then added a new line (thus, $$$n = 2, \: a = [2, 0]$$$). Polycarp first added a new line and then changed the line with the number $$$5$$$ (thus, $$$m = 2, \: b = [0, 5]$$$).Since the initial length of the file was $$$3$$$, in order for Polycarp to change line number $$$5$$$ two new lines must be added beforehand. Examples of correct sequences of changes, in this case, would be $$$[0, 2, 0, 5]$$$ and $$$[2, 0, 0, 5]$$$. Changes $$$[0, 0, 5, 2]$$$ (wrong order of actions) and $$$[0, 5, 2, 0]$$$ (line $$$5$$$ cannot be edited yet) are not correct.

Input: The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$). Then $$$t$$$ test cases follow. Before each test case, there is an empty line.Each test case contains three lines. The first line contains three integers $$$k$$$, $$$n$$$, $$$m$$$ ($$$0 \le k \le 100$$$, $$$1 \le n, m \le 100$$$) — the initial number of lines in file and lengths of Monocarp's and Polycarp's sequences of changes respectively.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 300$$$).The third line contains $$$m$$$ integers $$$b_1, b_2, \dots, b_m$$$ ($$$0 \le b_j \le 300$$$).

Output: For each test case print any correct common sequence of Monocarp's and Polycarp's actions of length $$$n + m$$$ or -1 if such sequence doesn't exist.


Sample Inputs:
5

3 2 2
2 0
0 5

4 3 2
2 0 5
0 6

0 2 2
1 0
2 3

5 4 4
6 0 8 0
0 7 0 9

5 4 1
8 7 8 0
0

Sample Outputs:
2 0 0 5 
0 2 0 6 5 
-1
0 6 0 7 0 8 0 9
-1

Solution (Python):
def solve():
    input()
    (k, n1, n2) = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    (ai, bi) = (0, 0)
    res = []
    zeros = 0
    while ai + bi < n1 + n2:
        if ai < n1 and a[ai] == 0:
            res.append(0)
            zeros += 1
            ai += 1
        elif bi < n2 and b[bi] == 0:
            res.append(0)
            zeros += 1
            bi += 1
        elif ai < n1 and a[ai] <= k + zeros:
            res.append(a[ai])
            ai += 1
        elif bi < n2 and b[bi] <= k + zeros:
            res.append(b[bi])
            bi += 1
        else:
            print(-1)
            return
    print(' '.join(map(str, res)))
for _ in range(int(input())):
    solve()

Solution (Python):
def editorial_solve(k, n, a, m, b):
    ans = []
    lines = k
    (i, j) = (0, 0)
    while i < n or j < m:
        if i < n and a[i] == 0:
            lines += 1
            ans.append(a[i])
            i += 1
        elif j < m and b[j] == 0:
            lines += 1
            ans.append(b[j])
            j += 1
        elif i < n and a[i] <= lines:
            ans.append(a[i])
            i += 1
        elif j < m and b[j] <= lines:
            ans.append(b[j])
            j += 1
        else:
            print(-1)
            return
    print(' '.join(map(str, ans)))

def solve(k, n, a, m, b):
    ans = []
    lines = k
    (i, j) = (0, 0)
    while i < n and j < m:
        if a[i] == 0:
            lines += 1
            ans.append(a[i])
            i += 1
        elif b[j] == 0:
            lines += 1
            ans.append(b[j])
            j += 1
        elif a[i] > 0:
            if a[i] <= lines:
                ans.append(a[i])
                i += 1
            elif b[j] <= lines:
                ans.append(b[j])
                j += 1
            else:
                print(-1)
                return
    while j < m:
        if b[j] == 0:
            lines += 1
            ans.append(b[j])
            j += 1
        elif b[j] <= lines:
            ans.append(b[j])
            j += 1
        else:
            print(-1)
            return
    while i < n:
        if a[i] == 0:
            lines += 1
            ans.append(a[i])
            i += 1
        elif a[i] <= lines:
            ans.append(a[i])
            i += 1
        else:
            print(-1)
            return
    print(' '.join(map(str, ans)))
for t in range(int(input())):
    empty_line = input()
    (k, n, m) = map(int, input().split())
    a = list(map(int, list(input().split())))
    b = list(map(int, list(input().split())))
    editorial_solve(k, n, a, m, b)

Solution (Python):
def solve(k, n, a, m, b):
    ans = []
    lines = k
    (i, j) = (0, 0)
    while i < n and j < m:
        if a[i] == 0:
            lines += 1
            ans.append(a[i])
            i += 1
        elif b[j] == 0:
            lines += 1
            ans.append(b[j])
            j += 1
        elif a[i] > 0:
            if a[i] <= lines:
                ans.append(a[i])
                i += 1
            elif b[j] <= lines:
                ans.append(b[j])
                j += 1
            else:
                print(-1)
                return
    while j < m:
        if b[j] == 0:
            lines += 1
            ans.append(b[j])
            j += 1
        elif b[j] <= lines:
            ans.append(b[j])
            j += 1
        else:
            print(-1)
            return
    while i < n:
        if a[i] == 0:
            lines += 1
            ans.append(a[i])
            i += 1
        elif a[i] <= lines:
            ans.append(a[i])
            i += 1
        else:
            print(-1)
            return
    print(' '.join(map(str, ans)))
for t in range(int(input())):
    empty_line = input()
    (k, n, m) = map(int, input().split())
    a = list(map(int, list(input().split())))
    b = list(map(int, list(input().split())))
    solve(k, n, a, m, b)