結果

問題 No.1056 2D Lamps
コンテスト
ユーザー convexineq
提出日時 2020-05-15 23:02:05
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 1,451 ms / 3,000 ms
コード長 1,525 bytes
コンパイル時間 111 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 37,476 KB
最終ジャッジ日時 2024-09-19 12:33:22
合計ジャッジ時間 15,393 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

def get_generator(n):
    v = (1<<n)-1
    res = [v<<(n*i) for i in range(n)]
    v = 0
    for i in range(n):
        v ^= 1<<(i*n)
    res += [v<<i for i in range(n)]
    
    r = [0]*(2*n-1)
    s = [0]*(2*n-1)
    for i in range(n):
        for j in range(n):
            r[i+j] ^= 1<<(n*i+j)
            s[i-j+n-1] ^= 1<<(n*i+j)
    res += r+s
    return res


def get_basis(a):
    basis = [] #基底をためる配列
    for e in a:
        for b in basis:
            if e > e^b: e = e^b
        if e: basis.append(e)
    return basis

def normalize(v,basis,length):
    for e,l in zip(basis,length):
        if v&(1<<(l-1)):
            v ^= e
    return v

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline 

#n,q,*m = list(map(int,read().split()))
n,m = map(int,readline().split())

MOD = (1<<32)-1
basis = get_basis(get_generator(n))
length = [i.bit_length() for i in basis]
#print(get_generator(n))
#print(basis)
#print(length)


mat = "".join(read().split())
d = {}

for T in range(m):
    c = "".join("0" if j=="." else "1" for j in mat[T*n*n:(T+1)*n*n])
    #print(c,int(c,2),"c")
    key = normalize(int(c,2),basis,length)
    #print(key)
    if key in d:
        d[key].append(T)
    else:
        d[key] = [T]


#print(d)

ans = [["0"]*m for i in range(m)]
for k,v in d.items():
    for a in v:
        for b in v:
            if a < b: ans[a][b] = "1"

#print(*("".join(i) for i in ans),sep="\n")

for i in range(m-1):
    print("".join(ans[i][i+1:]))
0