結果

問題 No.1056 2D Lamps
ユーザー gew1fw
提出日時 2025-06-12 19:24:22
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,759 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 82,040 KB
実行使用メモリ 54,648 KB
最終ジャッジ日時 2025-06-12 19:24:31
合計ジャッジ時間 6,311 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

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 = 0
        for i in range(N):
            line = data[idx].strip()
            idx += 1
            for j in range(N):
                if line[j] == '#':
                    pos = i * N + j
                    grid |= (1 << pos)
        grids.append(grid)

    # Generate all operation vectors
    operation_vectors = []

    # Rows
    for k in range(1, N+1):
        vec = 0
        for j in range(1, N+1):
            pos = (k-1)*N + (j-1)
            vec |= (1 << pos)
        operation_vectors.append(vec)

    # Columns
    for k in range(1, N+1):
        vec = 0
        for i in range(1, N+1):
            pos = (i-1)*N + (k-1)
            vec |= (1 << pos)
        operation_vectors.append(vec)

    # Diag1: i + j = k
    min_k_diag1 = 2
    max_k_diag1 = 2 * N
    for k in range(min_k_diag1, max_k_diag1 + 1):
        vec = 0
        for i in range(1, N+1):
            j = k - i
            if 1 <= j <= N:
                pos = (i-1)*N + (j-1)
                vec |= (1 << pos)
        operation_vectors.append(vec)

    # Diag2: i - j = l
    min_l_diag2 = -(N-1)
    max_l_diag2 = N-1
    for l in range(min_l_diag2, max_l_diag2 + 1):
        vec = 0
        for i in range(1, N+1):
            j = i - l
            if 1 <= j <= N:
                pos = (i-1)*N + (j-1)
                vec |= (1 << pos)
        operation_vectors.append(vec)

    # Gaussian elimination
    basis = []
    for vec in operation_vectors:
        current = vec
        for (p, b) in basis:
            if (current >> p) & 1:
                current ^= b
        if current != 0:
            p = current.bit_length() - 1
            inserted = False
            for i in range(len(basis)):
                if basis[i][0] < p:
                    basis.insert(i, (p, current))
                    inserted = True
                    break
            if not inserted:
                basis.append((p, current))

    # Prepare the result
    result = []
    for i in range(M):
        for j in range(i + 1, M):
            d = grids[i] ^ grids[j]
            current = d
            for (p, b) in basis:
                if (current >> p) & 1:
                    current ^= b
            if current == 0:
                result.append('1')
            else:
                result.append('0')

    # Output the result
    ptr = 0
    for i in range(M - 1):
        line = []
        for j in range(i + 1, M):
            line.append(result[ptr])
            ptr += 1
        print(''.join(line))
    print()

if __name__ == '__main__':
    main()
0