結果

問題 No.1056 2D Lamps
ユーザー convexineqconvexineq
提出日時 2020-05-15 23:00:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,643 ms / 3,000 ms
コード長 1,525 bytes
コンパイル時間 346 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 149,136 KB
最終ジャッジ日時 2024-09-19 12:30:02
合計ジャッジ時間 9,030 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
53,412 KB
testcase_01 AC 34 ms
52,352 KB
testcase_02 AC 40 ms
52,256 KB
testcase_03 AC 2,615 ms
148,944 KB
testcase_04 AC 2,587 ms
148,448 KB
testcase_05 AC 2,542 ms
148,736 KB
testcase_06 AC 2,587 ms
148,640 KB
testcase_07 AC 2,607 ms
148,992 KB
testcase_08 AC 2,502 ms
148,984 KB
testcase_09 AC 1,797 ms
148,728 KB
testcase_10 AC 1,866 ms
149,056 KB
testcase_11 AC 2,643 ms
148,912 KB
testcase_12 AC 2,533 ms
149,136 KB
testcase_13 AC 35 ms
53,512 KB
testcase_14 AC 47 ms
65,252 KB
testcase_15 AC 55 ms
66,904 KB
testcase_16 AC 52 ms
66,120 KB
権限があれば一括ダウンロードができます

ソースコード

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