Overview

In this problem, we are given an \(H \times W\) grid of light bulbs and perform \(Q\) operations, each toggling the state of a specified cell and its adjacent cells (up, down, left, and right). We need to find the final state of the grid. Since each operation affects at most \(5\) cells, it is sufficient to simply toggle only those \(5\) cells directly.

Analysis

Key Observation

First, note that the state of each light bulb changes only by toggling. Since toggling is equivalent to the XOR (exclusive OR) operation, it has the following properties:

• Toggling the same cell twice restores it to its original state.
• The order of toggles does not affect the result.

Therefore, “simulating the operations in order” and “counting how many times each cell is toggled and checking its parity” yield the exact same result.

Naive Approaches and Their Pitfalls

Here are two common pitfalls to avoid:

(1) Scanning the entire grid on every operation

If you implement it by scanning all cells on every operation, checking whether each cell should be toggled, the time complexity becomes \(O(QHW) = \text{up to } 10^5 \times 10^6 = 10^{11}\), which will definitely result in TLE (Time Limit Exceeded).

However, in reality, each operation only changes the state of at most \(5\) cells: $\((r, c),\ (r, c-1),\ (r, c+1),\ (r-1, c),\ (r+1, c)\)\( By modifying only these cells directly, each operation can be processed in \)O(1)$ time.

(2) Rebuilding strings on every operation

In Python, modifying a string like S[i] = S[i][:j] + ('1' if ... ) + S[i][j+1:] creates a copy that takes \(O(W)\) time per operation. Since \(W\) can be up to \(10^6\), doing this for \(Q = 10^5\) operations is fatal. Because Python strings are immutable, we need to use a mutable data structure.

Solution Strategy

• Store the grid as a 1D mutable byte sequence (bytearray).
• Map cell \((i, j)\) (\(1\)-indexed) to index \(p = (i-1) \times W + (j-1)\).
• A toggle can be performed with a single instruction: grid[p] ^= 1.

A neat trick here is storing the characters '0' and '1' directly in the bytearray. In ASCII, '0' = \(48 = \texttt{0b110000}\) and '1' = \(49 = \texttt{0b110001}\), meaning only the least significant bit differs. Thus, simply executing ^= 1 flips '0' \(\leftrightarrow\) '1', completely eliminating the need for conversions between numbers and characters. It can also be written out directly as a byte sequence when printing the output.

Algorithm

1. Read the entire input at once using sys.stdin.buffer.read().split().
2. Concatenate \(S_1, \dots, S_H\) to form a bytearray of length \(HW\) (this represents the grid).
3. For each operation \((R_k, C_k)\), let \(p = (R_k-1)W + (C_k-1)\) and perform:
   • grid[p] ^= 1
   • If \(C_k > 1\), grid[p-1] ^= 1 (left)
   • If \(C_k < W\), grid[p+1] ^= 1 (right)
   • If \(R_k > 1\), grid[p-W] ^= 1 (up)
   • If \(R_k < H\), grid[p+W] ^= 1 (down)
4. Finally, split grid into chunks of \(W\) characters, insert newlines between them, and output everything at once.

Example

For \(H = W = 3\), suppose the initial state is:

000
000
000

When the switch at \((2,2)\) is pressed, \(p = 1\cdot 3 + 1 = 4\), and cells \(p, p-1, p+1, p-3, p+3\) = \(4, 3, 5, 1, 7\) are toggled, resulting in:

010
111
010

Furthermore, pressing \((1,1)\) gives \(p = 0\). Since the left and top neighbors are out of bounds, cells \(0, 1, 3\) are toggled, yielding:

100
011
010

Complexity

• Time Complexity: \(O(HW + Q)\)
• Space Complexity: \(O(HW)\)

Since \(HW \le 10^6\) and \(Q \le 10^5\), this is well within the time limit.

Implementation Details

• Speed up I/O: Since \(HW \le 10^6\) and \(Q \le 10^5\), calling input() for each line is too slow. Read the entire input at once using sys.stdin.buffer.read().split(), and collect the output in a bytearray to write it out at once using sys.stdout.buffer.write.

• Use a 1D bytearray instead of a 2D list: Using a list of lists increases memory usage and reference overhead. Flattening the grid to 1D using the index formula \(p = (i-1)W + (j-1)\) is both fast and memory-efficient.

• Toggling using ASCII properties: In ASCII, '0' (48) and '1' (49) differ only in their least significant bit, so toggling can be done with ^= 1. This avoids converting to int or creating str objects, and allows printing directly.

• Do not forget boundary checks: Boundary cells do not have all four neighbors. In particular, because the grid is flattened into 1D, accessing p-1 when c == 1 will inadvertently toggle the end of the previous row (this is dangerous because it will not raise an out-of-bounds error, but will result in WA). Be sure to include all four checks: if c > 1, if c < W, if r > 1, and if r < H.

• Be careful when \(W\) is not explicitly given in the input: Although an upper bound on \(W\) is not explicitly stated in the constraints, \(HW \le 10^6\) implies that \(W\) itself can be up to \(10^6\). Ensure that boundary checks work correctly for both wide cases (\(H = 1\)) and tall cases (\(W = 1\)).

• Concatenating output: Calling print \(H\) times (up to \(2\times10^4\) times) row-by-row is also slow, so it is safer to append slices using a memoryview to a bytearray and output everything together at the end.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    H = int(data[0]); W = int(data[1])
    grid = bytearray(b''.join(data[2:2 + H]))
    Q = int(data[2 + H])
    idx = 3 + H
    for _ in range(Q):
        r = int(data[idx]); c = int(data[idx + 1]); idx += 2
        p = (r - 1) * W + (c - 1)
        grid[p] ^= 1
        if c > 1:
            grid[p - 1] ^= 1
        if c < W:
            grid[p + 1] ^= 1
        if r > 1:
            grid[p - W] ^= 1
        if r < H:
            grid[p + W] ^= 1
    mv = memoryview(grid)
    out = bytearray()
    for i in range(H):
        out += mv[i * W:(i + 1) * W]
        out += b'\n'
    sys.stdout.buffer.write(bytes(out))

main()

---

This editorial was generated by claude5opus-high.