Overview

This is a simulation problem where you need to find the timing when one of the candidates has 0 supporters, as students’ support changes over time.

Analysis

In this problem, we need to sequentially update students’ support status while managing the number of supporters for Takahashi and Aoki.

A naive approach would be to scan all students each time to recalculate the supporter counts, but this requires \(O(N)\) computation per speech, resulting in \(O(NM)\) overall. Given the constraints \(N, M \leq 2 \times 10^5\), this could reach up to \(4 \times 10^{10}\) operations, which will not fit within the time limit (TLE).

Instead, we record which candidate each student currently supports, and for each speech, we flip that student’s support while simultaneously incrementing/decrementing the supporter counts for Takahashi and Aoki. This allows updates in constant time.

Furthermore, after each speech, we check whether either candidate’s supporter count has reached 0 to determine if the simulation should terminate early.

Algorithm

1. Count the initial number of supporters for Takahashi and Aoki.
2. Prepare an array to record each student’s current support (True: Takahashi, False: Aoki, etc.).
3. For each speech, do the following:
   • Flip the specified student’s support.
   • Update the corresponding candidate’s supporter count accordingly (decrease for the one who lost support, increase for the one who gained it).
   • After the update, if either candidate’s supporter count becomes 0, output that speech number and terminate.
4. If all speeches have been processed and both candidates still have supporters, output -1.

Complexity

• Time complexity: \(O(N + M)\)
  (\(O(N)\) for the initial count, \(O(1)\) × \(M\) times for processing each speech)
• Space complexity: \(O(N)\)
  (array to store support status)

Implementation Notes

• Student numbers are given in 1-indexed form, so they need to be converted to 0-indexed for internal processing (R[i] - 1).

• The change in supporter count is always exactly 1 person, so it can be accurately tracked with +=1 and -=1.

• Once the election result is determined, immediately return to terminate the program.

  Source Code

import sys

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    S = data[2]
    R = list(map(int, data[3:3+M]))
    
    # カウント初期化
    taka = S.count('T')
    aoki = S.count('A')
    
    # 各生徒の現在の支持者を管理する配列（True: Taka, False: Aoki）
    support = [True if c == 'T' else False for c in S]
    
    for i in range(M):
        r = R[i] - 1  # 0-indexedに変換
        
        if support[r]:  # 現在 高橋君を支持している
            taka -= 1
            aoki += 1
            support[r] = False
        else:  # 現在 青木君を支持している
            aoki -= 1
            taka += 1
            support[r] = True
        
        # 演説後にどちらかの支持者が0人になったかチェック
        if taka == 0 or aoki == 0:
            print(i + 1)
            return
    
    # すべての演説が終わった後も両方に支持者がいる場合
    print(-1)

if __name__ == "__main__":
    main()

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