Overview

For each scholarship, we need to select from among the applicants the one with “the highest evaluation score, and if tied, the smallest applicant number.”

Analysis

Problem Breakdown

This problem allows us to determine the recipient for each scholarship independently. Since scholarships do not affect each other, we simply need to perform the following process for each scholarship:

1. Get the list of students who applied for that scholarship
2. If the list is empty, output \(0\)
3. If the list is not empty, select the applicant with “maximum evaluation score” and “smallest number if tied”

Is a Naive Approach Acceptable?

Checking the constraints: - Number of scholarships \(N \leq 2 \times 10^5\) - Total number of applicants across all scholarships \(\sum_{i=1}^{N} K_i \leq 2 \times 10^5\)

This constraint is crucial. Even with a method that examines all applicants for each scholarship, the total number of applicants examined is at most \(2 \times 10^5\) times.

In other words, a naive approach that linearly scans the applicants for each scholarship is sufficiently fast.

Algorithm

1. Read input: Store the applicants’ evaluation score list \(P\) in an array
2. Process each scholarship:
   • Read the number of applicants \(K_i\) and the applicant list
   • If \(K_i = 0\), the answer is \(0\)
   • If \(K_i \geq 1\), scan the applicant list to find the optimal applicant
3. How to select the optimal applicant:
   • Maintain the current best candidate (best) and best score (best_score)
   • For each applicant \(c\):
     • If \(c\)’s evaluation score is greater than best_score → update
     • If \(c\)’s evaluation score equals best_score and \(c\) is smaller than best → update

Concrete Example

For example, if scholarship 1 has applicants \(\{3, 1, 2\}\) and the evaluation scores are \(P = [100, 150, 150]\): - Applicant 3: evaluation score \(150\) - Applicant 1: evaluation score \(100\) - Applicant 2: evaluation score \(150\)

The highest score is \(150\), which applies to applicants 2 and 3. Applicant 2, having the smaller number, becomes the recipient.

Complexity

• Time complexity: \(O(M + \sum_{i=1}^{N} K_i)\)
  • \(O(M)\) for reading evaluation scores
  • Processing each scholarship is proportional to the number of applicants, totaling \(O(\sum K_i)\)
• Space complexity: \(O(M + \max K_i)\)
  • \(O(M)\) for the evaluation score array
  • At most \(O(\max K_i)\) for each scholarship’s applicant list (since we process sequentially)

Implementation Notes

• 1-indexed and 0-indexed conversion: Applicant numbers start from \(1\) (1-indexed), but the array \(P\) starts from \(0\) (0-indexed). The evaluation score for applicant \(c\) is accessed as P[c-1]

• Input format caution: Each scholarship line has the format “\(K_i\) \(C_{i,1}\) … \(C_{i,K_i}\)”. Note that when \(K_i = 0\), there are no applicant numbers following it

• Fast input: Using sys.stdin.readline allows for fast processing of large amounts of input

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    P = list(map(int, input().split()))
    
    results = []
    for _ in range(N):
        line = list(map(int, input().split()))
        K = line[0]
        if K == 0:
            results.append(0)
        else:
            candidates = line[1:K+1]
            # Find the candidate with highest score, tie-break by smallest index
            best = None
            best_score = -1
            for c in candidates:
                score = P[c - 1]  # c is 1-indexed, P is 0-indexed
                if score > best_score or (score == best_score and c < best):
                    best_score = score
                    best = c
            results.append(best)
    
    print('\n'.join(map(str, results)))

if __name__ == '__main__':
    main()

---

This editorial was generated by claude4.5opus.