結果

問題 No.1056 2D Lamps
ユーザー convexineqconvexineq
提出日時 2020-05-15 23:02:05
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 1,802 ms / 3,000 ms
コード長 1,525 bytes
コンパイル時間 167 ms
コンパイル使用メモリ 12,016 KB
実行使用メモリ 36,656 KB
最終ジャッジ日時 2023-10-19 16:27:32
合計ジャッジ時間 18,462 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 30 ms
10,288 KB
testcase_01 AC 30 ms
10,288 KB
testcase_02 AC 30 ms
10,288 KB
testcase_03 AC 1,772 ms
36,656 KB
testcase_04 AC 1,758 ms
36,656 KB
testcase_05 AC 1,749 ms
36,656 KB
testcase_06 AC 1,777 ms
36,656 KB
testcase_07 AC 1,759 ms
36,656 KB
testcase_08 AC 1,802 ms
36,656 KB
testcase_09 AC 1,251 ms
36,656 KB
testcase_10 AC 1,342 ms
36,656 KB
testcase_11 AC 1,751 ms
36,656 KB
testcase_12 AC 1,759 ms
36,656 KB
testcase_13 AC 29 ms
10,288 KB
testcase_14 AC 37 ms
10,608 KB
testcase_15 AC 34 ms
10,624 KB
testcase_16 AC 35 ms
10,636 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