Three Sevens (Codeforces 1798B)
Tags: Greedy, data structures

Lottery "Three Sevens" was held for $$$m$$$ days. On day $$$i$$$, $$$n_i$$$ people with the numbers $$$a_{i, 1}, \ldots, a_{i, n_i}$$$ participated in the lottery.It is known that in each of the $$$m$$$ days, only one winner was selected from the lottery participants. The lottery winner on day $$$i$$$ was not allowed to participate in the lottery in the days from $$$i+1$$$ to $$$m$$$.Unfortunately, the information about the lottery winners has been lost. You need to find any possible list of lottery winners on days from $$$1$$$ to $$$m$$$ or determine that no solution exists.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 50\,000$$$). The description of the test cases follows.The first line of each test case contains a single integer $$$m$$$ ($$$1 \le m \le 50\,000$$$) — the number of days in which the lottery was held.Next, for each $$$i$$$ from $$$1$$$ to $$$m$$$, follows a two-line block of data.The first line of each block contains a single integer $$$n_i$$$ ($$$1 \le n_i \le 50\,000$$$) — the number of lottery participants on day $$$i$$$.The second line of the block contains integers $$$a_{i, 1}, \ldots, a_{i, n_i}$$$ ($$$1 \le a_{i, j} \le 50\,000$$$) — lottery participants on day $$$i$$$. It is guaranteed that all the numbers $$$a_{i, 1}, \ldots, a_{i, n_i}$$$ are pairwise distinct.It is guaranteed that the sum of $$$n_i$$$ over all blocks of all test cases does not exceed $$$50\,000$$$.

Output: For each test case, if there is no solution, print a single integer $$$-1$$$.Otherwise, print $$$m$$$ integers $$$p_1, p_2, \ldots, p_m$$$ ($$$1 \le p_i \le 50\,000$$$) — lottery winners on days from $$$1$$$ to $$$m$$$. If there are multiple solutions, print any of them.

Note: In the first test case, one of the answers is $$$[8, 2, 1]$$$ since the participant with the number $$$8$$$ participated on day $$$1$$$, but did not participate on days $$$2$$$ and $$$3$$$; the participant with the number $$$2$$$ participated on day $$$2$$$, but did not participate on day $$$3$$$; and the participant with the number $$$1$$$ participated on day $$$3$$$. Note that this is not the only possible answer, for example, $$$[8, 9, 4]$$$ is also a correct answer.In the second test case, both lottery participants participated on both days, so any possible lottery winner on the day $$$1$$$ must have participated on the day $$$2$$$, which is not allowed. Thus, there is no correct answer.In the third test case, only one participant participated on days $$$2$$$, $$$3$$$, $$$4$$$, and on day $$$1$$$ there is only one participant who did not participate in the lottery on days $$$2, 3, 4$$$ — participant $$$2$$$, which means $$$[2, 1, 4, 3]$$$ is the only correct answer to this test case.

Sample Inputs:
3
3
4
1 2 4 8
3
2 9 1
2
1 4
2
2
1 2
2
2 1
4
4
1 2 3 4
1
1
1
4
1
3

Sample Outputs:
8 2 1 
-1
2 1 4 3

Solution (Python):
import sys
import heapq
import math
input = sys.stdin.readline
from collections import Counter, deque, defaultdict

def sieve_of_eratosthenes(n):
    if n < 2:
        return []
    sieve = [True] * (n + 1)
    (sieve[0], sieve[1]) = (False, False)
    primes = []
    for current in range(2, int(n ** 0.5) + 1):
        if sieve[current]:
            primes.append(current)
            for multiple in range(current * current, n + 1, current):
                sieve[multiple] = False
    for current in range(int(n ** 0.5) + 1, n + 1):
        if sieve[current]:
            primes.append(current)
    return primes

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    s = input()
    return list(s[:len(s) - 1])

def invr():
    return map(int, input().split())

def count_divisible_by(num, limit):
    return limit // num

def sum_range(a, b):
    return b * (b + 1) // 2 - a * (a - 1) // 2

def solve():
    m = inp()
    days = []
    for _ in range(m):
        n = inp()
        days.append(inlt())
    last_app = {}
    for (i, ls) in enumerate(days):
        for contestant in ls:
            last_app[contestant] = i + 1
    output = [-1 for _ in range(m)]
    for (contestant, day) in last_app.items():
        output[day - 1] = contestant
    if all([val != -1 for val in output]):
        print(*output)
    else:
        print(-1)

def main():
    for _ in range(inp()):
        solve()
main()

Solution (Python):
from io import StringIO
from collections import OrderedDict
import sys

def main():
    out = StringIO()
    get_line = sys.stdin.readline

    def get_ints():
        return map(int, get_line().split(' '))

    def get_int():
        return int(get_line())
    tc = get_int()
    for i in range(tc):
        m = get_int()
        g = []
        ans = []
        lasts = {}
        for j in range(m):
            _ = get_int()
            a = get_ints()
            for k in a:
                lasts[k] = j
        skeys = sorted(lasts.items(), key=lambda x: x[1])
        cur = 0
        ans = []
        for j in range(m):
            while cur < len(skeys):
                if skeys[cur][1] == j:
                    ans.append(str(skeys[cur][0]))
                    break
                cur += 1
            else:
                ans = ['-1']
                break
        out.write(' '.join(ans) + '\n')
    sys.stdout.write(out.getvalue())
if __name__ == '__main__':
    main()

Solution (Python):
from collections import *
from functools import *
import sys
input = lambda : sys.stdin.readline().rstrip()
Z = int(input())
for _ in range(Z):
    days = int(input())
    ans = [0] * days
    dic = defaultdict(list)
    for day in range(days):
        n = int(input())
        (*arr,) = map(int, input().split())
        for i in arr:
            dic[i].append(day)
    for (i, j) in dic.items():
        d = j[-1]
        if not ans[d]:
            ans[d] = i
    if ans.count(0) == 0:
        print(' '.join(map(str, ans)))
    else:
        print(-1)