結果

問題 No.460 裏表ちわーわ
コンテスト
ユーザー ciel
提出日時 2017-03-08 15:12:23
言語 Ruby
(3.4.1)
結果
AC  
実行時間 317 ms / 2,000 ms
コード長 1,727 bytes
コンパイル時間 96 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 14,208 KB
最終ジャッジ日時 2024-06-23 18:59:12
合計ジャッジ時間 6,388 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

#!/usr/bin/ruby
def popcnt(n)
	r=0
	while n>0
		r+=n%2
		n/=2
	end
	r
end

def lightsout(x,y)
	a=(x*y).times.map{[0,0]}

	#create problem
	x.times{|i|
		y.times{|j|
			a[i+j*x][0]=1<<(i+j*x)
			a[i+j*x][1]= 0 +
				(1<<(i+j*x)) |
				(i>0   ? 1<<(i-1+j*x) : 0) |
				(i<x-1 ? 1<<(i+1+j*x) : 0) |
				(j>0   ? 1<<(i+(j-1)*x) : 0) |
				(j<y-1 ? 1<<(i+(j+1)*x) : 0) |
				(i>0   && j>0   ? 1<<(i-1+(j-1)*x) : 0) |
				(i<x-1 && j>0   ? 1<<(i+1+(j-1)*x) : 0) |
				(i>0   && j<y-1 ? 1<<(i-1+(j+1)*x) : 0) |
				(i<x-1 && j<y-1 ? 1<<(i+1+(j+1)*x) : 0) |
				0;
		}
	}

	#solve
	badbits=0
	(x*y).times{|i|
		if (a[i][1]&(1<<i))==0
			if (i+1...x*y).each{|j|
				if (a[j][1]&(1<<i))!=0
					a[i],a[j]=a[j],a[i]
					break
				end
			} then
				badbits|=1<<i
				next
			end
		end

		(x*y).times{|j|
			next if i==j
			if (a[j][1]&(1<<i))!=0
				a[j][0]^=a[i][0]
				a[j][1]^=a[i][1]
			end
		}
	}
	k=x*y-popcnt(badbits)
	STDERR.puts "quiet pattern=%d"%[x*y-k]

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

	#入力・解の存在判定
	input=0
	y.times{|j|
		a=gets.split.map(&:to_i)
		x.times{|i|
			input|=a[i]<<j*x+i
		}
	}
	if t.any?{|e|popcnt(e&input)%2>0}
		return -1
	end

	tlst=[0]*(1<<(x*y-k))
	(1<<(x*y-k)).times{|l|
		r=0
		(x*y-k).times{|j|
			if (l&(1<<j))>0
				r^=t[j]
			end
		}
		tlst[l]=r
	}

	r0=1<<29
	c0=0
	a_ok.each{|j|
		if (input&(1<<j[0]))>0
			c0^=j[1]
		end
	}
	#0解の重ね合わせをすべて試す
	(1<<(x*y-k)).times{|l|
		r1=c0
		r1^=tlst[l]
		r0=[r0,popcnt(r1)].min
	}
	r0
end

while gets
	m,n=$_.split.map(&:to_i)
	r=lightsout(n,m)
	puts r<0 ? :Impossible : r
end
0