Overview

Calculate the total score for each student (sum of scores for correctly answered problems), then output the rank as “number of people with a higher score + 1” in descending order of score. Students with the same score receive the same rank.

Analysis

First, each student’s total score can be computed by scanning the string \(S_i\) from left to right and adding the score \(P_j\) for each position where the character is o.

Next, for ranking, it might seem sufficient to sort by score in descending order and use the position. However, there are caveats:

• Handling ties: If you simply use “sorted index + 1” as the rank, students with the same score would get different ranks (e.g., if two students both have 100 points, they would be ranked 1st and 2nd).
• Sorting everyone and assigning ranks can work correctly, but you need to manage “groups of tied scores.”

A cleaner and more reliable approach is to count the number of people at each score (frequency distribution), then accumulate “the number of people with higher scores” from the top to determine ranks.

Example: If scores are [80, 100, 80, 60] - 100 points: count 1 → people with higher score: 0 → rank 1 - 80 points: count 2 → people with higher score: 1 → rank 2 - 60 points: count 1 → people with higher score: 3 → rank 4

This way, tied scores receive the same rank.

Algorithm

1. Store the given scores \(P_1 \ldots P_M\) in an array.
2. For each student, scan the string \(S_i\), adding the score of each problem marked o to compute the total score scores[i].
3. Use a Counter (associative array) to count “score → number of people.”
4. Sort only the distinct scores (keys) in descending order.
5. Iterating from the highest score downward:
   • The rank for that score = (number of people seen so far = number of people with a higher score) + 1
   • Then add the count of people with that score to “number of people seen so far”
   • Store the result in rankmap[score].
6. Finally, for each student, look up rankmap using their score scores[i] and output the rank.

Complexity

• Time complexity: Computing total scores is \(O(NM)\) (with the constraint \(NM \le 5\times 10^6\)). Sorting the distinct score types, with \(K\) being the number of distinct scores, is \(O(K\log K)\). Overall: \(O(NM + K\log K)\)
• Space complexity: scores is \(O(N)\), Counter and rankmap are \(O(K)\), so the total is \(O(N+K)\)

Implementation Notes

• Since the input is large, using sys.stdin.buffer.readline makes it faster.

• In Python, receiving strings as bytes and checking b == 111 (ord('o')) can be slightly faster.

• Ranks are determined by “cumulative count of higher-scoring people + 1,” and using a Counter (count per score) makes it easy to ensure that tied scores receive the same rank.

  Source Code

import sys
from collections import Counter

def main():
    input = sys.stdin.buffer.readline
    N, M = map(int, input().split())
    P = list(map(int, input().split()))

    scores = []
    for _ in range(N):
        s = input().rstrip()  # bytes
        total = 0
        for j, b in enumerate(s):
            if b == 111:  # ord('o')
                total += P[j]
        scores.append(total)

    cnt = Counter(scores)
    uniq = sorted(cnt.keys(), reverse=True)

    rankmap = {}
    higher = 0
    for sc in uniq:
        rankmap[sc] = higher + 1
        higher += cnt[sc]

    out = "\n".join(str(rankmap[sc]) for sc in scores)
    sys.stdout.write(out)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.