Overview

Given \(N\) students, find the passing students whose scores are at least \(L\) and at most \(R\), and determine the attendance number of the student with the highest score among them.

Analysis

To solve this problem, we focus on the following points.

Problem Breakdown

1. Passing condition: Score is at least \(L\) and at most \(R\)
2. What to find: The attendance number of the student with the highest score among passing students
3. Tie-breaking: Choose the student with the smallest attendance number
4. If there are no passing students: Output -1

Is a Naive Approach Sufficient?

\(N\) is at most \(2 \times 10^5\). Since we only need to examine each student once to make a judgment, this takes \(O(N)\) time, so there are no computational complexity issues.

Handling Ties

There is a condition that “if multiple students have the highest score, choose the one with the smallest attendance number.” This is naturally satisfied by iterating from the beginning and updating only when a strictly higher score is found.

For example, if the scores are [70, 80, 80, 60] with \(L=60\), \(R=100\): - Student 1 (70 points): Current highest → update - Student 2 (80 points): Higher than 70 → update - Student 3 (80 points): Same as 80 → do not update (this preserves attendance number 2) - Student 4 (60 points): Lower than 80 → do not update

As a result, attendance number 2 is the answer.

Algorithm

1. Initialize variable max_score to \(-1\) (no passing student found yet) and result to \(-1\) (no answer yet)
2. Iterate through students in order of attendance number (\(i = 0, 1, 2, \ldots, N-1\))
3. For each student:
   • If score \(P_i\) is at least \(L\) and at most \(R\) (satisfies the passing condition), and
   • Score \(P_i\) is greater than the current max_score
   • → Update max_score to \(P_i\) and update result to \(i + 1\) (attendance numbers are 1-indexed)
4. Output the final result

Complexity

• Time complexity: \(O(N)\)
  • Because we iterate through all students once
• Space complexity: \(O(N)\)
  • Because we store the score list \(P\)

Implementation Notes

1. Attendance numbers are 1-indexed: Since array indices start from 0, when outputting the answer, we need to use i + 1.

2. Update condition is “strictly greater than”: By using the condition P[i] > max_score, in the case of a tie, the student found first (with the smaller attendance number) is preserved. If we used >= instead, a later student with the same score would overwrite the earlier one.

3. Initial value setting: By setting max_score = -1, we can correctly detect passing students even with a score of 0 (since scores range from \(0\) to \(100\), \(-1\) is a value that cannot occur).

   Source Code

N, L, R = map(int, input().split())
P = list(map(int, input().split()))

max_score = -1
result = -1

for i in range(N):
    if L <= P[i] <= R:
        if P[i] > max_score:
            max_score = P[i]
            result = i + 1

print(result)

---

This editorial was generated by claude4.5opus.