結果

問題 No.460 裏表ちわーわ
ユーザー cielciel
提出日時 2017-03-08 15:12:23
言語 Ruby
(3.3.0)
結果
AC  
実行時間 308 ms / 2,000 ms
コード長 1,727 bytes
コンパイル時間 66 ms
コンパイル使用メモリ 11,264 KB
実行使用メモリ 17,348 KB
最終ジャッジ日時 2023-09-05 23:48:35
合計ジャッジ時間 6,673 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 86 ms
15,256 KB
testcase_01 AC 81 ms
15,304 KB
testcase_02 AC 99 ms
15,236 KB
testcase_03 AC 81 ms
15,152 KB
testcase_04 AC 82 ms
15,028 KB
testcase_05 AC 88 ms
15,216 KB
testcase_06 AC 87 ms
15,228 KB
testcase_07 AC 84 ms
15,008 KB
testcase_08 AC 307 ms
17,172 KB
testcase_09 AC 88 ms
15,236 KB
testcase_10 AC 302 ms
17,164 KB
testcase_11 AC 84 ms
15,264 KB
testcase_12 AC 86 ms
15,112 KB
testcase_13 AC 302 ms
17,148 KB
testcase_14 AC 303 ms
17,160 KB
testcase_15 AC 306 ms
17,248 KB
testcase_16 AC 85 ms
15,316 KB
testcase_17 AC 308 ms
17,260 KB
testcase_18 AC 308 ms
17,188 KB
testcase_19 AC 306 ms
17,204 KB
testcase_20 AC 88 ms
15,028 KB
testcase_21 AC 306 ms
17,236 KB
testcase_22 AC 307 ms
17,052 KB
testcase_23 AC 305 ms
17,064 KB
testcase_24 AC 307 ms
17,348 KB
testcase_25 AC 83 ms
15,100 KB
testcase_26 AC 84 ms
15,160 KB
testcase_27 AC 82 ms
15,256 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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