結果

問題 No.460 裏表ちわーわ
ユーザー cielciel
提出日時 2017-03-09 14:33:22
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 328 ms / 2,000 ms
コード長 1,918 bytes
コンパイル時間 556 ms
コンパイル使用メモリ 11,100 KB
実行使用メモリ 10,176 KB
最終ジャッジ日時 2023-09-06 05:18:01
合計ジャッジ時間 6,026 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 18 ms
8,016 KB
testcase_01 AC 17 ms
8,096 KB
testcase_02 AC 39 ms
8,476 KB
testcase_03 AC 16 ms
8,096 KB
testcase_04 AC 16 ms
8,120 KB
testcase_05 AC 17 ms
8,036 KB
testcase_06 AC 18 ms
8,080 KB
testcase_07 AC 17 ms
8,028 KB
testcase_08 AC 323 ms
10,072 KB
testcase_09 AC 18 ms
8,040 KB
testcase_10 AC 325 ms
10,060 KB
testcase_11 AC 17 ms
8,048 KB
testcase_12 AC 17 ms
8,040 KB
testcase_13 AC 325 ms
10,168 KB
testcase_14 AC 324 ms
10,176 KB
testcase_15 AC 328 ms
10,104 KB
testcase_16 AC 17 ms
8,012 KB
testcase_17 AC 327 ms
10,072 KB
testcase_18 AC 321 ms
10,100 KB
testcase_19 AC 327 ms
10,104 KB
testcase_20 AC 18 ms
8,080 KB
testcase_21 AC 325 ms
10,064 KB
testcase_22 AC 322 ms
10,064 KB
testcase_23 AC 328 ms
10,068 KB
testcase_24 AC 322 ms
10,104 KB
testcase_25 AC 17 ms
8,080 KB
testcase_26 AC 17 ms
8,056 KB
testcase_27 AC 17 ms
8,188 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/python
#coding:utf-8
import sys
if sys.version_info[0]<3:
	input=raw_input
	range=xrange

def popcnt(n):
	r=0
	while n>0:
		r+=n%2
		n//=2
	return r

def lightsout(x,y):
	a=[[0,0] for _ in range(x*y)]

	#create problem
	for i in range(x):
		for j in range(y):
			a[i+j*x][0]=1<<(i+j*x)
			a[i+j*x][1]= 0 +\
				(1<<(i+j*x)) |\
				(1<<(i-1+j*x) if i>0   else 0) |\
				(1<<(i+1+j*x) if i<x-1 else 0) |\
				(1<<(i+(j-1)*x) if j>0   else 0) |\
				(1<<(i+(j+1)*x) if j<y-1 else 0) |\
				(1<<(i-1+(j-1)*x) if i>0   and j>0   else 0) |\
				(1<<(i+1+(j-1)*x) if i<x-1 and j>0   else 0) |\
				(1<<(i-1+(j+1)*x) if i>0   and j<y-1 else 0) |\
				(1<<(i+1+(j+1)*x) if i<x-1 and j<y-1 else 0) |\
				0

	#solve
	badbits=0
	for i in range(x*y):
		if (a[i][1]&(1<<i))==0:
			for j in range(i+1,x*y):
				if (a[j][1]&(1<<i))!=0:
					a[i],a[j]=a[j],a[i]
					break
			else:
				badbits|=1<<i
				continue
		for j in range(x*y):
			if i==j: continue
			if (a[j][1]&(1<<i))!=0:
				a[j][0]^=a[i][0]
				a[j][1]^=a[i][1]

	k=x*y-popcnt(badbits)
	#STDERR.puts "quiet pattern=%d"%[x*y-k]

	#0解(quiet pattern)の集合tを用意する
	tmsk=0
	t=[]
	a_ok=[]
	for i in range(x*y):
		if ((badbits>>i)&1):
			t.append(a[i][0])
		else:
			a_ok.append((i,a[i][0]))
			tmsk|=1<<i

	#入力・解の存在判定
	input_=0
	for j in range(y):
		a=list(map(int,input().split()))
		for i in range(x):
			input_|=a[i]<<j*x+i
	if any(popcnt(e&input_)%2 for e in t):
		return -1

	tlst=[0]*(1<<(x*y-k))
	for l in range(1<<(x*y-k)):
		r=0
		for j in range(x*y-k):
			if (l&(1<<j)):
				r^=t[j]
		tlst[l]=r

	r0=1<<29
	c0=0
	for j in a_ok:
		if (input_&(1<<j[0])):
			c0^=j[1]
	#0解の重ね合わせをすべて試す
	for l in range(1<<(x*y-k)):
		r1=c0
		r1^=tlst[l]
		r0=min(r0,popcnt(r1))
	return r0

try:
	while True:
		m,n=map(int,input().split())
		r=lightsout(n,m)
		print('Impossible' if r<0 else r)
except EOFError:
	pass
0