Overview

For each scholarship, select the person with the highest evaluation score among the applicants, and if there are ties, select the one with the smallest applicant number.

Analysis

In this problem, for each scholarship, we need to sort the applicants by “evaluation score in descending order, and by applicant number in ascending order if scores are the same,” then select the top-ranked person.

A straightforward approach would be to list the relevant applicants each time and sort them, but since the constraints are very large (\(N, M \sim 2 \times 10^5\)) and the total \(\sum K_i \leq 2 \times 10^5\), efficient processing is required.

For this problem, fast input handling is necessary to pass the online judge, and the overhead of each sort needs to be close to constant time. Since Python’s standard input is slow, we need to use sys.stdin.read to read all input at once.

Fortunately, the number of candidates \(K_i\) for each scholarship is relatively small, and the total sum does not exceed \(2 \times 10^5\), so listing the candidates and sorting them each time is fast enough.

Algorithm

1. First, store the evaluation scores of all applicants in an array \(P\) (indexed by applicant number).
2. For each scholarship:
   • If there are no applicants (\(K_i = 0\)), output 0.
   • If there are applicants:
     • Store pairs of each applicant’s evaluation score and number \((P[c], c)\) in a list.
     • Sort this list by “evaluation score in descending order → applicant number in ascending order.”
     • The first element is the scholarship recipient, so output that applicant’s number.

Complexity

• Time complexity: \(O(\sum K_i \log (\max K_i))\) (time required for sorting per scholarship)
• Space complexity: \(O(M + \max K_i)\)

Implementation Notes

• Since the input is very large, use sys.stdin.read to read everything at once and then split it.

• Applicant numbers are 1-indexed, so the evaluation score array \(P\) should also be stored as 1-indexed.

• By using (-score, id) as the sort key, we achieve descending order by evaluation score and ascending order by ID.

• Collecting results and outputting them all at once at the end is faster (print('\n'.join(result))).

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    P = [0] * (M + 1)
    for j in range(1, M + 1):
        P[j] = int(data[idx])
        idx += 1

    result = []
    for _ in range(N):
        K = int(data[idx])
        idx += 1
        if K == 0:
            result.append('0')
            continue
        candidates = []
        for __ in range(K):
            c = int(data[idx])
            idx += 1
            candidates.append((P[c], c))
        # Sort by score descending, then by ID ascending
        candidates.sort(key=lambda x: (-x[0], x[1]))
        winner = candidates[0][1]
        result.append(str(winner))
    
    print('\n'.join(result))

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.