lcb-0078

1.000

4/4 tests· algorithms

Proposed solution

I'll solve this step by step.

## Problem Understanding

1. We have N people with scores P_i
2. We need to assign ranks based on scores, where:
   - Higher scores get better (lower rank numbers)
   - People with the same score get the same rank
   - The ranking process works by repeatedly finding the maximum remaining score and assigning ranks

## Algorithm Approach

Let me trace through the first example to understand:
- Scores: [3, 12, 9, 9] (indices 1,2,3,4)
- Step 1: Max score is 12 → person 2 gets rank 1 → r = 2
- Step 2: Max score among remaining is 9 → persons 3,4 get rank 2 → r = 4  
- Step 3: Max score among remaining is 3 → person 1 gets rank 4 → r = 5

## Implementation Plan

1. Read input
2. Create list of (score, index) pairs
3. Sort by score in descending order
4. Process scores in descending order, assigning ranks
5. Handle ties properly - people with same score get same rank

Let me think more carefully about the algorithm:
- We want to process from highest score to lowest
- For each unique score value, we assign the current rank to all people with that score
- The rank increases by the count of people with that score

## Refined Approach

1. Create pairs of (score, person_index) 
2. Sort by score descending
3. Process in order, keeping track of current rank and how many people have same score
4. For each group of people with same score, assign them the same rank

Let me trace again:
- People: [3, 12, 9, 9] 
- Sorted by score desc: [(12,2), (9,3), (9,4), (3,1)]
- Process (12,2): rank=1, assign to person 2 → rank becomes 2
- Process (9,3) and (9,4): rank=2, assign to persons 3,4 → rank becomes 4  
- Process (3,1): rank=4, assign to person 1 → rank becomes 5

## Code Implementation

```python
n = int(input())
scores = list(map(int, input().split()))

# Create list of (score, original_index) pairs (1-indexed)
score_index_pairs = [(scores[i], i+1) for i in range(n)]

# Sort by score in descending order
score_index_pairs.sort(reverse=True)

# Initialize result array
ranks = [0] * n

# Current rank
current_rank = 1

# Process scores in descending order
i = 0
while i < len(score_index_pairs):
    # Get current score
    current_score = score_index_pairs[i][0]
    
    # Find all people with this score
    same_score_count = 0
    j = i
    while j < len(score_index_pairs) and score_index_pairs[j][0] == current_score:
        same_score_count += 1
        j += 1
    
    # Assign same rank to all people with this score
    k = i
    while k < i + same_score_count:
        original_index = score_index_pairs[k][1] - 1  # Convert back to 0-indexed
        ranks[original_index] = current_rank
        k += 1
    
    # Update rank for next group
    current_rank += same_score_count
    i += same_score_count

# Output results
for rank in ranks:
    print(rank)
```

Test output (stdout)

....                                                                     [100%]
4 passed in 0.06s

System prompt

You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.