Overview

For each light, this problem asks you to determine the final state (ON or OFF) after pressing its switch \(K_i\) times.

Analysis

Pressing a switch once toggles the state of the light (ON \(\to\) OFF, or OFF \(\to\) ON). Now, let’s consider what happens when the switch is pressed twice: - Starting from ON and pressing twice: ON \(\to\) OFF \(\to\) ON - Starting from OFF and pressing twice: OFF \(\to\) ON \(\to\) OFF

As we can see, pressing the switch twice returns it to its original state. Therefore, regarding the number of presses \(K_i\), we can state the following: - When \(K_i\) is even: the final state is the same as the initial state - When \(K_i\) is odd: the final state is toggled from the initial state

If we naively simulate the \(K_i\) toggles using a for loop as described in the problem statement, since \(K_i\) can be up to \(10^9\), this would exceed the time limit and result in TLE (Time Limit Exceeded). However, by focusing on the parity (remainder when divided by 2) of \(K_i\) as described above, we can determine the final state instantly without any loops.

Algorithm

For each light \(i\), perform the following: 1. Compute the remainder of \(K_i\) divided by 2. 2. If the remainder is 1 (odd): - If the initial state \(S_i\) is Yes, add No to the output. - If the initial state \(S_i\) is No, add Yes to the output. 3. If the remainder is 0 (even): - Add the initial state \(S_i\) as-is to the output.

After processing all lights, output the results separated by newlines.

Complexity

• Time complexity: \(O(N)\)
  • The parity check and state toggle for each light can be done in \(O(1)\). Since this is repeated \(N\) times, the overall time complexity is \(O(N)\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for reading the input data at once and for storing the list of output results.

Implementation Notes

• Fast I/O: Since the amount of input/output data can be large (\(N \leq 10^5\)), in Python it is much faster to read all input at once using sys.stdin.read().split() and output all results at once using sys.stdout.write() with join, rather than calling input() or print() multiple times.

• Parity check: You can check parity using K % 2 == 1 (odd) or K % 2 == 0 (even). As a more advanced alternative, you can use the bitwise operation K & 1 to check for oddness.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    
    results = []
    idx = 1
    for _ in range(N):
        S = input_data[idx]
        K = int(input_data[idx+1])
        idx += 2
        
        if K % 2 == 1:
            if S == "Yes":
                results.append("No")
            else:
                results.append("Yes")
        else:
            results.append(S)
            
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.1-pro-thinking.