Overview

Given an \(H \times W\) sheet, we stamp the same \(R \times C\) stamp \(N\) times, and we need to determine and output which cells are # in the final result.

Analysis

Key Observations

• The stamping operation “sets the corresponding cells to # (takes the OR).” Cells that are already # remain unchanged.
• Even if part of the stamp extends beyond the sheet, we only need to apply the portion that falls within the sheet (range clipping is required).

Why the Naive Approach is Difficult

The naive approach scans all cells of the stamp for each stamping operation:

• If a cell is #, reflect it onto the sheet.

This gives a time complexity of at most \(O(NRC)\). At maximum constraints, this is about \(1000 \times 100 \times 100 = 10^7\) operations, which might pass in some languages, but in Python, boundary checks and string operations tend to add up, leaving little room.

Solution Strategy (Speedup with Bit Sets)

In this code, we speed things up by representing each row of the sheet as a bit string stored as an integer.

• Each row is represented as a bit string of length \(W\) (# as 1, . as 0)
• Each row of the stamp is similarly converted to a bit string
• The stamping operation can be processed for each relevant row using just board[row] |= (stamp_row_bits << shift) (or right shift) — a “bitwise OR” and “shift”

This allows us to update everything in a single integer operation instead of updating \(C\) cells one by one.

Algorithm

1. Convert the stamp to bits row by row

   • Convert ./# to 0/1, and represent each row as an int in binary.
   • In the implementation, the string is reversed with [::-1] to “place the leftmost column in the least significant bit.”
     This allows column offsets to be expressed simply as shifts.

2. Store each row of the sheet as an integer (bit string)

   • board[i] is the bit representation of row \(i\) (0-indexed) of the sheet.
   • Since nothing has been stamped yet, all values start at 0.

3. Process each stamp operation

   • The input \((r, c)\) is 1-indexed, so convert to 0-indexed as top=r-1, left=c-1.
   • Considering overflow, compute the actual range of overlapping stamp rows:
     • i_start (starting row on the stamp side)
     • i_end (ending row on the stamp side, half-open interval) This is the clipping step.
   • Column overflow is handled via shifts:
     • If left >= 0, use stamp_bits[i] << left
     • If left < 0, use stamp_bits[i] >> (-left)
   • To prevent bits beyond the sheet width \(W\) from being set, we always apply & mask where mask=(1<<W)-1.
   • Finally, reflect the result with board[top+i] |= shifted_bits.

4. Output

   • Convert each row’s integer to a \(W\)-digit binary string using format(row, f"0{W}b"),
   • Reverse with [::-1] to restore the original column order,
   • Replace 0/1 with ./# and output.

Complexity

• Time complexity: \(O(NR)\) (bitwise operations for the number of overlapping rows per stamp)
  • Strictly speaking, Python’s arbitrary-precision integer arithmetic cost is involved, but since \(W \le 1000\), it is sufficiently small and fast in practice.
• Space complexity: \(O(H)\) (storing the sheet as one integer per row) + \(O(R)\) for the stamp

Implementation Notes

• Coordinate clipping is the most critical part. Cases where top is negative (overflows above) or top+R exceeds \(H\) (overflows below) are correctly trimmed using i_start and i_end.

• Column overflow: if left is negative, right-shifting handles it naturally (though there is a light conditional branch since the result may become 0 after shifting).

• Using mask = (1<<W)-1 and applying & mask ensures that bits outside the sheet (to the right of column \(W\)) are always cleared, which is safe.

• Input/output is optimized using sys.stdin.buffer.read(), split(), and bytes.maketrans.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)

    H = int(next(it))
    W = int(next(it))
    R = int(next(it))
    C = int(next(it))

    tr_in = bytes.maketrans(b".#", b"01")
    stamp_bits = []
    for _ in range(R):
        s = next(it)
        stamp_bits.append(int(s[::-1].translate(tr_in), 2))

    N = int(next(it))

    board = [0] * H
    mask = (1 << W) - 1

    for _ in range(N):
        r = int(next(it))
        c = int(next(it))
        top = r - 1
        left = c - 1

        # Quick reject if no overlap
        if top >= H or top <= -R or left >= W or left <= -C:
            continue

        i_start = 0 if top >= 0 else -top
        i_end = R if H - top >= R else H - top
        if i_start >= i_end:
            continue

        if left >= 0:
            shift = left
            for i in range(i_start, i_end):
                b = stamp_bits[i]
                if b:
                    board[top + i] |= (b << shift) & mask
        else:
            s = -left
            for i in range(i_start, i_end):
                b = stamp_bits[i]
                if b:
                    shifted = b >> s
                    if shifted:
                        board[top + i] |= shifted & mask

    tr_out = str.maketrans("01", ".#")
    out_lines = []
    fmt = f"0{W}b"
    for row in board:
        out_lines.append(format(row, fmt)[::-1].translate(tr_out))
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.