結果
問題 | No.1056 2D Lamps |
ユーザー |
![]() |
提出日時 | 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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
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:]))