Overview

Given applicants for each of \(N\) types of scholarships, the problem asks you to identify the “person with the highest evaluation score (or the person with the smallest number in case of a tie)” for each scholarship.

Analysis

The key to this problem is accurately managing the association between “who applied” for each scholarship and “what their evaluation score is”.

1. Managing Evaluation Scores

By storing the evaluation scores \(P_j\) in an array (list) indexed by applicant number \(j\), we can reference any score in \(O(1)\) time. Since applicant numbers range from \(1\) to \(M\), it is efficient to prepare an array of size \(M+1\).

2. Rules for Determining Recipients

The conditions for selecting one person from the applicants for each scholarship are as follows: - In principle, select the person with the maximum evaluation score \(P_j\). - If multiple people have the maximum evaluation score, select the one with the smallest applicant number \(j\) among them.

This comparison process can be implemented by checking each applicant for a given scholarship one by one and updating the “current best applicant.”

3. Complexity Estimation

The number of scholarships \(N\), the total number of applicants \(M\), and the total number of applications across all scholarships \(\sum K_i\) are all at most \(2 \times 10^5\). Since we check and compare each applicant once, the total number of operations is proportional to \(\sum K_i\). This runs sufficiently fast and fits within the time limit.

Algorithm

1. Store the evaluation scores \(P_1, \ldots, P_M\) in an array P.
2. For each scholarship \(i = 1, \ldots, N\), perform the following:
   • If the number of applicants \(K_i\) is \(0\), output 0.
   • If \(K_i > 0\), check the applicants \(C_{i,k}\) for that scholarship in order.
   • Prepare variables max_p (maximum evaluation score) and best_c (the applicant number at that time), and update them whenever a better candidate appears.
     • Update if “current applicant’s score > max_p” or “current score == max_p and current number < best_c”.
   • Output the final best_c.

Complexity

• Time complexity: \(O(N + M + \sum K_i)\)
  • Reading all evaluation scores takes \(O(M)\), scanning all scholarships takes \(O(N)\), and the comparison processing for all applicants takes a total of \(O(\sum K_i)\). Since each constraint is on the order of \(2 \times 10^5\), the overall number of operations is approximately \(6 \times 10^5\), which is sufficiently fast.
• Space complexity: \(O(M + \sum K_i)\)
  • The array storing evaluation scores uses \(O(M)\), and reading input all at once uses \(O(\sum K_i)\) memory.

Implementation Tips

• Fast I/O: In Python, when the amount of input data is large, reading all input at once using sys.stdin.read().split() is significantly faster than repeatedly calling input().

• Initial value setting: When comparing for the maximum evaluation score, setting the initial value of max_p to a value at or below the minimum possible evaluation score (\(1\)), such as \(-1\), allows the update process to work smoothly.

• Handling 1-indexed values: Since applicant numbers start from \(1\), setting the array size to \(M+1\) to align indices helps prevent mistakes.

  Source Code

import sys

def solve():
    # 入力を一括で読み込み、イテレータを作成して高速にアクセスできるようにします。
    # この手法は、大規模な入力データを扱う競技プログラミングにおいてPythonでよく使われる高速化手法です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    
    # 奨学金の種類数 N と、応募者の人数 M を取得します。
    try:
        N = int(next(it))
        M = int(next(it))
    except StopIteration:
        return
    
    # 各応募者の評価点 P_1, P_2, ..., P_M を取得します。
    # 応募者番号は1から始まるため、1-indexedでリストに格納します。
    P = [0] * (M + 1)
    for i in range(1, M + 1):
        P[i] = int(next(it))
        
    results = []
    # 各奨学金について受給者を決定します。
    for _ in range(N):
        try:
            K = int(next(it))
        except StopIteration:
            break
            
        # 応募者がいない場合は 0 を出力リストに追加します。
        if K == 0:
            results.append("0")
            continue
        
        # 受給者を決定するための変数を初期化します。
        # best_c: 現在の最高評価点を持つ応募者の中で最も小さい番号
        # max_p: 現在の最高評価点
        best_c = -1
        max_p = -1
        
        # この奨学金に応募した K 人の応募者についてループを回します。
        for _ in range(K):
            c = int(next(it))
            p_c = P[c]
            
            # 選択ルール:
            # 1. 評価点が最も高い応募者を選ぶ。
            # 2. 評価点が同じ場合は、応募者番号が最も小さい応募者を選ぶ。
            if p_c > max_p:
                max_p = p_c
                best_c = c
            elif p_c == max_p:
                if c < best_c:
                    best_c = c
        
        # 決定した応募者番号を文字列として結果リストに追加します。
        results.append(str(best_c))
    
    # すべての結果を改行で区切って一度に出力します。
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.