結果

問題 No.1056 2D Lamps
ユーザー convexineqconvexineq
提出日時 2020-05-15 23:00:39
言語 PyPy3
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,525 bytes
コンパイル時間 206 ms
コンパイル使用メモリ 81,816 KB
実行使用メモリ 148,044 KB
最終ジャッジ日時 2023-10-19 16:24:13
合計ジャッジ時間 31,033 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 35 ms
53,560 KB
testcase_01 AC 35 ms
53,560 KB
testcase_02 AC 35 ms
53,560 KB
testcase_03 TLE -
testcase_04 TLE -
testcase_05 TLE -
testcase_06 TLE -
testcase_07 TLE -
testcase_08 TLE -
testcase_09 AC 2,130 ms
147,968 KB
testcase_10 AC 2,321 ms
147,968 KB
testcase_11 TLE -
testcase_12 TLE -
testcase_13 AC 35 ms
53,560 KB
testcase_14 AC 50 ms
64,396 KB
testcase_15 AC 56 ms
66,504 KB
testcase_16 AC 53 ms
66,472 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