University Promotion (Editorial)

Solution

The problem is a simulation of a matching process based on specific priority rules. The core of the challenge lies in correctly ordering the students and efficiently checking their preferences. As per the rules:

1. Students are processed by score a_i in strictly decreasing order.

2. For tied scores, the student with the smaller index $i$ is processed first.

3. A student is admitted to the first major $j$ in their list where a_i > b_j and c_j > 0.

Since the number of majors $m$ is very small (m \le 50) and the total number of preferences \sum k_i is at most 5 \times 10^6, we can simply simulate the process. We sort the student indices using a custom comparator to handle the tie-breaking condition. Then, for each student in the sorted order, we iterate through their preference list and assign them to the first available major that satisfies the score threshold.

The complexity is O(n \log n + \sum k_i)

def solve():
    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    p=[]
    for i in range(n):
        r=list(map(int,input().split()))
        k=r[0]
        p.append(r[1:k+1])
    b=list(map(int,input().split()))
    c=list(map(int,input().split()))
    order=list(range(n))
    order.sort(key=lambda i:a[i],reverse=1)
    ans=[-1]*n
    for i in order:
        score=a[i]
        for major in p[i]:
            j=major-1
            if(score>b[j] and c[j]>0):
                ans[i]=major
                c[j]-=1
                break
    print(*ans)

for _ in range(int(input())):
    solve()