Overview

This is a problem where participants are paired according to specific rules, and we need to find the partner of participant number \(1\).

Analysis

In this problem, each participant has a “priority” assigned, and participants choose their pair partner in order from highest to lowest priority. The chosen partner is the person with the “smallest number” among those who are pair candidates with the current participant and have not yet been paired with anyone.

This greedy selection approach looks simple at first glance, but if we search for the minimum-numbered candidate for every participant each time, the worst case becomes \(O(N^2)\), which is too slow for the constraint \(N \leq 2 \times 10^5\).

However, if we maintain an “adjacency list” for each participant, we can make the candidate search process efficient. Specifically, we just scan person \(x\)’s adjacency list and choose the smallest-numbered person who has not yet been paired. This allows the candidate search to be performed quickly.

Furthermore, since we need to process participants in order of decreasing priority, using a “max heap” is appropriate. In Python, heapq is a min heap, so we can simulate a max heap by negating the priority values.

Finally, we need to maintain an array recording whether each person has been paired, to ensure we don’t match with someone who is already paired.

Algorithm

1. Read each participant’s priority \(R_i\) and build a max heap using entries of the form \((-R_i, i)\).
2. Create an adjacency list (undirected graph) from the pair candidates.
3. Pop one person at a time from the heap. If that person is not yet paired, scan their adjacency list and pair them with the smallest-numbered unpaired candidate.
4. Repeat this until everyone is paired.
5. Finally, output the partner of participant number \(1\).

Complexity

• Time complexity: \(O(M + N \log N)\)
  • \(O(N \log N)\) for heap construction and operations, and \(O(M)\) total for scanning adjacency lists.
• Space complexity: \(O(N + M)\)
  • \(O(N + M)\) for the adjacency lists and various management arrays.

Implementation Notes

• To process in order of decreasing priority, push \((-R_i, i)\) into heapq.

• Holding each node’s adjacency list as a list makes candidate searching efficient.

• Don’t forget to update the flag array paired that tracks whether each person has already been paired.

• If Aoki (number \(1\)) has been paired, output their partner.

  Source Code

import heapq
import sys

input = sys.stdin.read

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    R = [0] * (N + 1)
    for i in range(1, N + 1):
        R[i] = int(data[i + 1])
    
    # 隣接リストの構築
    adj = [[] for _ in range(N + 1)]
    idx = N + 2
    for _ in range(M):
        u = int(data[idx])
        v = int(data[idx + 1])
        adj[u].append(v)
        adj[v].append(u)
        idx += 2
    
    # 優先度が高い順に処理するためのヒープ
    # (-R[i], i) で最大ヒープをシミュレート
    heap = []
    for i in range(1, N + 1):
        heapq.heappush(heap, (-R[i], i))
    
    # 各人のペア状態を管理
    paired = [False] * (N + 1)
    partner = [-1] * (N + 1)
    
    while heap:
        _, x = heapq.heappop(heap)
        if paired[x]:
            continue
        
        # x の隣接点の中で、まだペアが決まっていない最小番号を探す
        candidates = []
        for neighbor in adj[x]:
            if not paired[neighbor]:
                candidates.append(neighbor)
        
        if not candidates:
            continue  # ただし問題文よりこれは起こらない
        
        y = min(candidates)
        
        # x と y をペアにする
        paired[x] = True
        paired[y] = True
        partner[x] = y
        partner[y] = x
    
    print(partner[1])

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.