結果
問題 |
No.1056 2D Lamps
|
ユーザー |
![]() |
提出日時 | 2025-06-12 16:57:29 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,930 bytes |
コンパイル時間 | 366 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 282,696 KB |
最終ジャッジ日時 | 2025-06-12 16:57:36 |
合計ジャッジ時間 | 6,797 ms |
ジャッジサーバーID (参考情報) |
judge1 / 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 boards = [] for _ in range(m): board = [] for _ in range(n): row = data[idx] idx +=1 board.append(row) boards.append(board) size_x = n size_y = n size_a = 2*n -1 size_b = 2*n -1 total_vars = size_x + size_y + size_a + size_b def get_col(var_type, k, n): if var_type == 'x': return k-1 elif var_type == 'y': return n + (k-1) elif var_type == 'a': return 2*n + (k-2) elif var_type == 'b': return 2*n + (2*n-1) + (k + (n-1)) else: return -1 def gaussian_elimination(equations, n_vars): rank =0 for col in reversed(range(n_vars)): pivot = -1 for i in range(rank, len(equations)): if (equations[i][0] >> col) &1: pivot = i break if pivot == -1: continue equations[rank], equations[pivot] = equations[pivot], equations[rank] for i in range(len(equations)): if i != rank and ( (equations[i][0] >> col) &1 ): equations[i] = ( equations[i][0] ^ equations[rank][0], equations[i][1] ^ equations[rank][1] ) rank +=1 for a, b in equations: if a ==0 and b !=0: return False return True output = [] for i in range(m): for j in range(i+1, m): d = [] for x in range(n): row = [] for y in range(n): a = boards[i][x][y] b = boards[j][x][y] row.append(1 if a != b else 0) d.append(row) equations = [] for x in range(1, n+1): for y in range(1, n+1): x_index = get_col('x', x, n) y_index = get_col('y', y, n) a_index = get_col('a', x + y, n) b_index = get_col('b', x - y, n) row_mask = 0 for idx_var in [x_index, y_index, a_index, b_index]: row_mask |= (1 << idx_var) rhs = d[x-1][y-1] equations.append( (row_mask, rhs) ) if gaussian_elimination(equations, total_vars): output.append('1') else: output.append('0') res = [] k = 0 for i in range(m-1): line = [] for j in range(i+1, m): line.append(output[k]) k +=1 res.append(''.join(line)) for line in res: print(line) print() if __name__ == "__main__": main()