結果
問題 | No.460 裏表ちわーわ |
ユーザー |
![]() |
提出日時 | 2020-09-27 03:58:54 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 951 ms / 2,000 ms |
コード長 | 1,348 bytes |
コンパイル時間 | 92 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 10,880 KB |
最終ジャッジ日時 | 2024-06-30 04:06:11 |
合計ジャッジ時間 | 11,611 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
import sysread=sys.stdin.buffer.readreadline=sys.stdin.buffer.readlinereadlines=sys.stdin.buffer.readlinesn, m=map(int, readline().split())a=list(map(int, read().split()))x=0for i, k in enumerate(a):if k:x^=(1<<i)def Gauss_Jordan(v):basis=[]idx=[]idxb=[]w=[0]*(len(v))for i, x in enumerate(v):y=xfor b, j in basis:if (y^b)<y:y^=bw[i]^=w[j]if y:w[i]^=(1<<i)basis.append((y, i))else:idx.append(i)return (basis, idx, w)v=[0]*(n*m)for i in range(n):for j in range(m):for dx in range(-1, 2):for dy in range(-1, 2):i1, j1=i+dx, j+dyif i1<0 or i1>=n or j1<0 or j1>=m:continuev[i*m+j]^=(1<<(i1*m+j1))basis, idx, w=Gauss_Jordan(v)z=xfor b, i in basis:if (z^b)<z:z^=bif z:print("Impossible")exit()k=len(idx)ans=n*mfor i in range(1<<k):x1=xcnt=0for j in range(k):if i&(1<<j):x1^=v[idx[j]]cnt+=1if x1==0:ans=min(ans, cnt)continuez=0for b, j in basis:if (x1^b)<x1:z^=w[j]x1^=bcnt+=bin(z).count('1')ans=min(ans, cnt)print(ans)