結果
問題 |
No.1056 2D Lamps
|
ユーザー |
![]() |
提出日時 | 2025-06-12 19:30:06 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,756 bytes |
コンパイル時間 | 189 ms |
コンパイル使用メモリ | 82,220 KB |
実行使用メモリ | 170,532 KB |
最終ジャッジ日時 | 2025-06-12 19:30:19 |
合計ジャッジ時間 | 5,474 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 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 A = [] for _ in range(M): grid = [] for _ in range(N): row = data[idx] idx +=1 grid.append(row) 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) A.append(vec) operations = [] # Type 1: rows for k in range(1, N+1): vec = 0 for j in range(1, N+1): i = k idx_bit = (i-1)*N + (j-1) vec |= (1 << idx_bit) operations.append(vec) # Type 2: columns for k in range(1, N+1): vec = 0 for i in range(1, N+1): j = k idx_bit = (i-1)*N + (j-1) vec |= (1 << idx_bit) operations.append(vec) # Type 3: diagonals i + j = s for s in range(2, 2*N +1): vec = 0 for i in range(1, N+1): j = s - i if 1 <= j <= N: idx_bit = (i-1)*N + (j-1) vec |= (1 << idx_bit) operations.append(vec) # Type 4: anti-diagonals i - j = t for t in range(-(N-1), N): vec = 0 for i in range(1, N+1): j = i - t if 1 <= j <= N: idx_bit = (i-1)*N + (j-1) vec |= (1 << idx_bit) operations.append(vec) # Gaussian Elimination basis = [] pivot_to_basis = {} for vec in operations: current = vec while current != 0: pivot = current.bit_length() - 1 if pivot in pivot_to_basis: current ^= pivot_to_basis[pivot] else: pivot_to_basis[pivot] = current basis.append(current) break # Check each pair B = [[0]*M for _ in range(M)] for i in range(M): for j in range(i+1, M): d = A[i] ^ A[j] current = d possible = True while current != 0: pivot = current.bit_length() -1 if pivot not in pivot_to_basis: possible = False break current ^= pivot_to_basis[pivot] if possible and current == 0: B[i][j] = 1 else: B[i][j] = 0 # Output the result for i in range(M-1): res = [] for j in range(i+1, M): res.append(str(B[i][j])) print(''.join(res)) print() if __name__ == '__main__': main()