Submission #13402510


Source Code Expand

Copy
# Studying https://atcoder.jp/contests/abc168/tasks/abc168_f
#      and https://mobile.twitter.com/chokudai/status/1262023105888698369

N,M = gets.split.map(&:to_i)
縦線 = N.times.map{ gets.split.map(&:to_i) }
横線 = M.times.map{ gets.split.map(&:to_i) }

経線 = 縦線.map{|_,_,c| c }.uniq.sort
緯線 = 横線.map{|d,| d }.uniq.sort

GW = 経線.size*2+3
GH = 緯線.size*2+3
GI = lambda{|横,縦|
	i = 経線.bsearch_index{|_| 横<=_ }||経線.size # 線分の端点の座標に対応する
	j = 緯線.bsearch_index{|_| 縦<=_ }||緯線.size
	i1 = 経線[i] != 横 ? 1 : 0 # 線分間の座標に対応するための補正
	j1 = 緯線[j] != 縦 ? 1 : 0
	next (2+2*j-j1)*GW+(2+2*i-i1)
}
Grid = lambda{|g|
	縦線.each{|a,b,c|
		GI[c,a].step(GI[c,b], GW){|i|
			g[i] = '0'
		}
	}
	i = 0
	GH.times{
		g[i] = g[i+GW-1] = '0'
		i += GW
	}

	横線.each{|d,e,f|
		GI[e,d].upto(GI[f,d]){|i|
			g[i] = '0'
		}
	}
	0.upto(GW-1){|i|
		g[i] = g[-1-i] = '0'
	}

	return g.to_i(2)
}['1'*(GW*GH)]
Area = lambda{|a|
	(GW+1).upto(GW+GW-2){|i|
		a[i] = a[-1-i] = Float::INFINITY
	}
	i = GW+1
	(GH-2).times{
		a[i] = a[i+GW-3] = Float::INFINITY
		i += GW
	}

	heights = 緯線.each_cons(2).map{|_1,_2| _2-_1 }
	widths = 経線.each_cons(2).map{|_1,_2| _2-_1 }
	j = (GW+1)*3
	heights.each{|h|
		i = 0
		widths.each{|w|
			a[j+i] = h*w
			i += 2
		}
		j += GW+GW
	}

	return a
}[[0]*(GW*GH)]

cow = 1 << GW*GH-1-GI[0,0]
while 0
	cow+ = (cow | cow>>1 | cow<<1 | cow>>GW | cow<<GW) & Grid
	break if cow == cow+
	cow = cow+
end

area = 0
until cow == 0
	a = cow ^ cow-1
	area += Area[-a.bit_length]
	cow &= ~a
end

puts(area.finite? ? area : 'INF')

Submission Info

Submission Time
Task F - . (Single Dot)
User ds14050
Language Ruby (2.7.1)
Score 0
Code Size 1726 Byte
Status
Exec Time 3315 ms
Memory 202824 KB

Compile Error

./Main.rb:53: warning: `_1' is reserved for numbered parameter; consider another name
./Main.rb:53: warning: `_2' is reserved for numbered parameter; consider another name
./Main.rb:54: warning: `_1' is reserved for numbered parameter; consider another name
./Main.rb:54: warning: `_2' is reserved for numbered parameter; consider another name
./Main.rb:73: warning: literal in condition

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt
Subtask1 0 / 600 sample_01.txt, sample_02.txt, sub1_01.txt, sub1_02.txt, sub1_03.txt, sub1_04.txt, sub1_05.txt, sub1_06.txt, sub1_07.txt, sub1_08.txt, sub1_09.txt, sub1_10.txt, sub1_11.txt, sub1_12.txt, sub1_13.txt, sub1_14.txt, sub1_15.txt, sub1_16.txt, sub1_17.txt, sub1_18.txt, sub1_19.txt, sub1_20.txt, sub1_21.txt, sub1_22.txt, sub1_23.txt, sub1_24.txt, sub1_25.txt, sub1_26.txt, sub1_27.txt, sub1_28.txt, sub1_29.txt, sub1_30.txt, sub1_31.txt, sub1_32.txt, sub1_33.txt, sub1_34.txt, sub1_35.txt, sub1_36.txt, sub1_37.txt, sub1_38.txt, sub1_39.txt, sub1_40.txt, sub1_41.txt, sub1_42.txt, sub1_43.txt, sub1_44.txt, sub1_45.txt, sub1_46.txt, sub1_47.txt, sub1_48.txt, sub1_49.txt, sub1_50.txt, sub1_51.txt, sub1_52.txt, sub1_53.txt, sub1_54.txt, sub1_55.txt, sub1_56.txt, sub1_57.txt, sub1_58.txt, sub1_59.txt, sub1_60.txt, sub1_61.txt, sub1_62.txt, sub1_63.txt, sub1_64.txt, sub1_65.txt, sub1_66.txt, sub1_67.txt, sub1_68.txt, sub1_69.txt, sub1_70.txt, sub1_71.txt, sub1_72.txt, sub1_73.txt, sub1_74.txt, sub1_75.txt, sub1_76.txt, sub1_77.txt, sub1_78.txt, sub1_79.txt, sub1_80.txt, sub1_81.txt, sub1_82.txt, sub1_83.txt, sub1_84.txt, sub1_85.txt, sub1_86.txt, sub1_87.txt, sub1_88.txt, sub1_89.txt, sub1_90.txt, sub1_91.txt, sub1_92.txt, sub1_93.txt, sub1_94.txt
Case Name Status Exec Time Memory
sample_01.txt 52 ms 14416 KB
sample_02.txt 53 ms 14400 KB
sub1_01.txt 274 ms 107488 KB
sub1_02.txt 268 ms 104904 KB
sub1_03.txt 109 ms 63288 KB
sub1_04.txt 109 ms 67568 KB
sub1_05.txt 1911 ms 167256 KB
sub1_06.txt 272 ms 106504 KB
sub1_07.txt 135 ms 58784 KB
sub1_08.txt 65 ms 18604 KB
sub1_09.txt 98 ms 24528 KB
sub1_10.txt 291 ms 59332 KB
sub1_11.txt 57 ms 15044 KB
sub1_12.txt 55 ms 14416 KB
sub1_13.txt 52 ms 14176 KB
sub1_14.txt 56 ms 14172 KB
sub1_15.txt 53 ms 14300 KB
sub1_16.txt 53 ms 14276 KB
sub1_17.txt 1716 ms 174100 KB
sub1_18.txt 3314 ms 179648 KB
sub1_19.txt 3314 ms 179636 KB
sub1_20.txt 3314 ms 179988 KB
sub1_21.txt 3314 ms 173212 KB
sub1_22.txt 3315 ms 193832 KB
sub1_23.txt 3314 ms 174844 KB
sub1_24.txt 3314 ms 181384 KB
sub1_25.txt 3314 ms 179364 KB
sub1_26.txt 3314 ms 178912 KB
sub1_27.txt 3314 ms 173780 KB
sub1_28.txt 3313 ms 156640 KB
sub1_29.txt 3315 ms 187212 KB
sub1_30.txt 3314 ms 161892 KB
sub1_31.txt 277 ms 111868 KB
sub1_32.txt 3312 ms 123936 KB
sub1_33.txt 3314 ms 166952 KB
sub1_34.txt 3314 ms 170532 KB
sub1_35.txt 3312 ms 117704 KB
sub1_36.txt 3314 ms 187832 KB
sub1_37.txt 3315 ms 193136 KB
sub1_38.txt 3312 ms 169952 KB
sub1_39.txt 799 ms 88716 KB
sub1_40.txt 3315 ms 192996 KB
sub1_41.txt 3313 ms 170608 KB
sub1_42.txt 51 ms 14492 KB
sub1_43.txt 56 ms 14412 KB
sub1_44.txt 52 ms 14372 KB
sub1_45.txt 55 ms 14328 KB
sub1_46.txt 52 ms 14360 KB
sub1_47.txt 491 ms 101032 KB
sub1_48.txt 665 ms 108868 KB
sub1_49.txt 375 ms 65828 KB
sub1_50.txt 160 ms 79836 KB
sub1_51.txt 780 ms 109604 KB
sub1_52.txt 824 ms 96572 KB
sub1_53.txt 600 ms 83900 KB
sub1_54.txt 753 ms 85384 KB
sub1_55.txt 3314 ms 177656 KB
sub1_56.txt 3315 ms 193140 KB
sub1_57.txt 3314 ms 168860 KB
sub1_58.txt 3314 ms 174196 KB
sub1_59.txt 3315 ms 191904 KB
sub1_60.txt 3315 ms 202824 KB
sub1_61.txt 1178 ms 158684 KB
sub1_62.txt 3315 ms 191812 KB
sub1_63.txt 66 ms 19476 KB
sub1_64.txt 3313 ms 153872 KB
sub1_65.txt 86 ms 45504 KB
sub1_66.txt 3314 ms 173992 KB
sub1_67.txt 1247 ms 134764 KB
sub1_68.txt 3313 ms 168808 KB
sub1_69.txt 3313 ms 176092 KB
sub1_70.txt 3313 ms 170672 KB
sub1_71.txt 52 ms 14304 KB
sub1_72.txt 56 ms 14552 KB
sub1_73.txt 51 ms 14348 KB
sub1_74.txt 227 ms 27864 KB
sub1_75.txt 96 ms 17572 KB
sub1_76.txt 547 ms 54336 KB
sub1_77.txt 62 ms 19468 KB
sub1_78.txt 64 ms 19380 KB
sub1_79.txt 75 ms 23788 KB
sub1_80.txt 79 ms 23932 KB
sub1_81.txt 78 ms 24228 KB
sub1_82.txt 92 ms 26504 KB
sub1_83.txt 53 ms 14232 KB
sub1_84.txt 75 ms 21672 KB
sub1_85.txt 91 ms 23900 KB
sub1_86.txt 52 ms 14452 KB
sub1_87.txt 54 ms 14512 KB
sub1_88.txt 53 ms 14244 KB
sub1_89.txt 412 ms 54088 KB
sub1_90.txt 408 ms 54144 KB
sub1_91.txt 429 ms 53884 KB
sub1_92.txt 411 ms 53972 KB
sub1_93.txt 427 ms 54024 KB
sub1_94.txt 52 ms 14308 KB