Overview

This is a problem where, after excluding withdrawn candidates, the top \(K\) candidates by score pass, and we need to determine whether Takahashi passes.

Analysis

To solve the problem, we need to create a list of candidates excluding those who withdrew, and check whether Takahashi is among the top \(K\) in that list. A naive approach of sorting all candidates and then removing withdrawn ones could break the sort order, making it impossible to compute correct rankings. Instead, removing withdrawn candidates first and then sorting is efficient, as only \(N-M\) candidates need to be sorted.

An important point is that the sorting condition is “in descending order of score, and in ascending order of candidate number for ties.” Since Takahashi’s number is 1, he has an advantage when scores are tied.

Algorithm

1. Read the input data
2. Create a set of withdrawn candidates
3. Create a list of candidates excluding withdrawn ones (each element is a tuple of (score, number))
4. Sort the created list in “descending order of score, ascending order of number”
5. Check the first \(K\) candidates in the sorted list — if Takahashi (number 1) is found, output “Yes”; otherwise, output “No”

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting is dominant, and with \(N\) up to 200,000, this is sufficiently fast
• Space complexity: \(O(N)\)
  • For storing the set of withdrawn candidates and the remaining candidate list

Implementation Notes

• Use a set data structure to manage withdrawn candidates, enabling \(O(1)\) membership checks

• By using (-score, number) as the sort key, descending order of score and ascending order of number can be specified simultaneously

• Return immediately once Takahashi is found to avoid unnecessary processing

• Be careful with input handling when \(M=0\) (the third line may not exist)

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print("No")
        return
        
    n = int(data[0])
    k = int(data[1])
    m = int(data[2])
    scores = list(map(int, data[3:3+n]))
    if m > 0:
        dropouts = set(map(int, data[3+n:3+n+m]))
    else:
        dropouts = set()
    
    # 高橋君の得点
    takahashi_score = scores[0]
    
    # 辞退者を除いた候補者を集計
    remaining = []
    for i in range(n):
        candidate_id = i + 1
        if candidate_id not in dropouts:
            remaining.append((scores[i], candidate_id))
    
    # 得点が高い順、同じ得点なら番号が小さい順にソート
    remaining.sort(key=lambda x: (-x[0], x[1]))
    
    # 上位K人の中に高橋君がいるか確認
    count = 0
    for score, candidate_id in remaining:
        count += 1
        if candidate_id == 1:
            print("Yes")
            return
        if count >= k:
            break
            
    print("No")

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.