結果
問題 |
No.1056 2D Lamps
|
ユーザー |
![]() |
提出日時 | 2025-06-12 19:26:58 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,795 bytes |
コンパイル時間 | 318 ms |
コンパイル使用メモリ | 82,108 KB |
実行使用メモリ | 124,976 KB |
最終ジャッジ日時 | 2025-06-12 19:27:18 |
合計ジャッジ時間 | 5,917 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | TLE * 1 -- * 13 |
ソースコード
def main(): import sys input = sys.stdin.read data = input().split() idx = 0 N = int(data[idx]) idx += 1 M = int(data[idx]) idx += 1 grids = [] for _ in range(M): grid = [] for _ in range(N): line = data[idx] idx += 1 grid.append(line) vec = 0 for i in range(N): for j in range(N): if grid[i][j] == '#': idx_bit = i * N + j vec |= (1 << idx_bit) grids.append(vec) operation_masks = [] # Rows for k in range(N): mask = 0 for j in range(N): idx_bit = k * N + j mask |= (1 << idx_bit) operation_masks.append(mask) # Columns for k in range(N): mask = 0 for i in range(N): idx_bit = i * N + k mask |= (1 << idx_bit) operation_masks.append(mask) # Diagonals i + j = d (d ranges from 0 to 2N-2) for d in range(2 * N - 1): mask = 0 for i in range(N): j = d - i if 0 <= j < N: idx_bit = i * N + j mask |= (1 << idx_bit) if mask != 0: operation_masks.append(mask) # Anti-diagonals i - j = d (d ranges from -(N-1) to N-1) for d in range(-(N-1), N): mask = 0 for i in range(N): j = i - d if 0 <= j < N: idx_bit = i * N + j mask |= (1 << idx_bit) if mask != 0: operation_masks.append(mask) # Gaussian elimination to find the basis basis = {} for mask in operation_masks: current = mask if current == 0: continue while True: pivot = current.bit_length() - 1 if pivot in basis: current ^= basis[pivot] if current == 0: break else: basis[pivot] = current break # Prepare the basis pivots in sorted order for checking pivots = sorted(basis.keys(), reverse=True) # Prepare the output output = [] for i in range(M): for j in range(i + 1, M): D = grids[j] ^ grids[i] temp = D for pivot in pivots: if (temp >> pivot) & 1: temp ^= basis[pivot] if temp == 0: output.append('1') else: output.append('0') # Print the output in the required format count = 0 for i in range(M - 1): line = output[count:count + (M - 1 - i)] print(''.join(line)) count += (M - 1 - i) if __name__ == "__main__": main()