Daycare Matching

from collections import deque

import heapq

​

def main():

    N, M = map(int, input().split())  # N = 児童数, M = 保育園数

    d = [[x-1 for x in list(map(int, input().split()))] for _ in range(N)]  # d[i][j] = 児童 i の第 j 希望保育園

    c = [[x-1 for x in list(map(int, input().split()))] for _ in range(M)]  # c[j][i] = 保育所 j の第 i 優先児童

    f = [[0]*N for _ in range(M)]  # f[j][i] = 保育所 j は児童 i を第何優先にしているか

    q = list(map(int, input().split()))  # q[j] = 保育所 j の受入人数

    for j in range(M):

        for i in range(N):

            f[j][c[j][i]] = i

​

    P = deque()  # P = 仮内定のない児童

    Q = [deque() for i in range(N)]  # Q[i] = 児童 i がまだ申し込んでいない保育園

    mu = [-1] * N  # mu[i] = 児童 i がマッチする保育園

    A = [[] for _ in range(M)]  # A[j] = 保育所 j が受け入れる児童の優先順位の集合

​

    for i in range(N):

        P.append(i)

        for j in range(M):

            Q[i].append(d[i][j])

​

    while P:

        i = P.popleft()

        j = Q[i].popleft()

        heapq.heappush(A[j], -f[j][i])

        mu[i] = j

        if len(A[j]) > q[j]:

            i = c[j][-heapq.heappop(A[j])]

            mu[i] = -1

            P.append(i)

​

    print(*[x+1 for x in mu])

​

if __name__ == '__main__':

    main()