Overview

This problem requires calculating the total score for each of \(N\) students from their test results, and then determining their rank based on those total scores. Students with the same score receive the same rank.

Analysis

Each student’s total score can be calculated by summing up the points for the problems they answered correctly. A naive approach would be to compute each student’s total score and then compare it against every other student’s score to determine the rank. However, this method takes \(O(N^2)\) time, and since \(N\) can be as large as \(2 \times 10^5\), it cannot be executed within the time limit.

To efficiently determine ranks, an effective approach is to sort all students’ total scores in descending order and use binary search to find where each student’s score is positioned in the sorted array. This allows the rank computation to be done in \(O(N \log N)\).

Algorithm

1. For each student, read their answer string and calculate their total score by summing up the points for the problems they answered correctly.
2. Sort all students’ total scores in descending order.
3. For each student’s total score, use binary search on the sorted array to find the number of students with a strictly higher score, and compute the rank (that count + 1).
   • In the binary search, we find the position (leftmost) where values strictly greater than the target score stop appearing in the sorted array.
   • The index at this position corresponds to the number of students with a strictly higher score than the target.

Complexity

• Time complexity: \(O(NM + N \log N)\)
  • Computing total scores takes \(O(NM)\), sorting takes \(O(N \log N)\), and binary search for each student’s rank takes \(O(N \log N)\).
  • Given the constraint \(N \times M \leq 5 \times 10^6\), \(NM\) is at most \(5 \times 10^6\), which is sufficiently fast.
• Space complexity: \(O(N)\)
  • This is for storing the list of total scores and the sorted list.

Implementation Notes

• When calculating total scores, match each student’s answer string with the point value list using indices.

• Sort in descending order, and in the binary search, find the boundary of “values greater than the target score” within the descending array.

• At the end of the binary search, left represents the number of students with a strictly higher score than the target, so the rank is left + 1.

  Source Code

import sys

def main():
    data = sys.stdin.read().splitlines()
    n, m = map(int, data[0].split())
    P = list(map(int, data[1].split()))
    
    scores = []
    total_scores = []
    
    for i in range(2, 2 + n):
        s = data[i].strip()
        scores.append(s)
        total = 0
        for j, char in enumerate(s):
            if char == 'o':
                total += P[j]
        total_scores.append(total)
    
    sorted_scores = sorted(total_scores, reverse=True)
    
    results = []
    for score in total_scores:
        left, right = 0, len(sorted_scores) - 1
        while left <= right:
            mid = (left + right) // 2
            if sorted_scores[mid] > score:
                left = mid + 1
            else:
                right = mid - 1
        rank = left + 1
        results.append(rank)
    
    for rank in results:
        print(rank)

if __name__ == "__main__":
    main()

---

This editorial was generated by deepseekv3.