Submission #13404210


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)
}
下 = lambda{|i|
	(i/GW+1)/2*2*GW + i%GW
}
上 = lambda{|i|
	i/GW/2*2*GW + i%GW
}
右 = lambda{|i|
	(i+1)/2*2
}
左 = lambda{|i|
	i/2*2
}
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 1896 Byte
Status
Exec Time 3313 ms
Memory 192548 KB

Compile Error

./Main.rb:65: warning: `_1' is reserved for numbered parameter; consider another name
./Main.rb:65: warning: `_2' is reserved for numbered parameter; consider another name
./Main.rb:66: warning: `_1' is reserved for numbered parameter; consider another name
./Main.rb:66: warning: `_2' is reserved for numbered parameter; consider another name
./Main.rb:85: 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 55 ms 14484 KB
sample_02.txt 56 ms 14436 KB
sub1_01.txt 278 ms 107788 KB
sub1_02.txt 273 ms 106876 KB
sub1_03.txt 106 ms 55360 KB
sub1_04.txt 109 ms 55736 KB
sub1_05.txt 1896 ms 163604 KB
sub1_06.txt 267 ms 106720 KB
sub1_07.txt 140 ms 59320 KB
sub1_08.txt 66 ms 18704 KB
sub1_09.txt 101 ms 24384 KB
sub1_10.txt 309 ms 59472 KB
sub1_11.txt 60 ms 15324 KB
sub1_12.txt 54 ms 14512 KB
sub1_13.txt 57 ms 14476 KB
sub1_14.txt 54 ms 14444 KB
sub1_15.txt 58 ms 14364 KB
sub1_16.txt 55 ms 14452 KB
sub1_17.txt 1730 ms 173236 KB
sub1_18.txt 3313 ms 180764 KB
sub1_19.txt 3313 ms 183580 KB
sub1_20.txt 3313 ms 181588 KB
sub1_21.txt 3312 ms 173440 KB
sub1_22.txt 3313 ms 186064 KB
sub1_23.txt 3313 ms 176740 KB
sub1_24.txt 3313 ms 184028 KB
sub1_25.txt 3313 ms 180368 KB
sub1_26.txt 3313 ms 178564 KB
sub1_27.txt 3312 ms 167192 KB
sub1_28.txt 3313 ms 159800 KB
sub1_29.txt 3312 ms 171932 KB
sub1_30.txt 3312 ms 170436 KB
sub1_31.txt 278 ms 112792 KB
sub1_32.txt 3312 ms 168904 KB
sub1_33.txt 3312 ms 156260 KB
sub1_34.txt 3312 ms 167788 KB
sub1_35.txt 3313 ms 185400 KB
sub1_36.txt 3312 ms 167784 KB
sub1_37.txt 3313 ms 186596 KB
sub1_38.txt 3311 ms 170748 KB
sub1_39.txt 810 ms 88788 KB
sub1_40.txt 3313 ms 192548 KB
sub1_41.txt 3312 ms 169684 KB
sub1_42.txt 59 ms 14388 KB
sub1_43.txt 58 ms 14348 KB
sub1_44.txt 57 ms 14332 KB
sub1_45.txt 54 ms 14384 KB
sub1_46.txt 57 ms 14356 KB
sub1_47.txt 1504 ms 109500 KB
sub1_48.txt 1203 ms 131692 KB
sub1_49.txt 1557 ms 109932 KB
sub1_50.txt 1172 ms 126384 KB
sub1_51.txt 1758 ms 109236 KB
sub1_52.txt 1646 ms 116936 KB
sub1_53.txt 1646 ms 109468 KB
sub1_54.txt 1235 ms 104236 KB
sub1_55.txt 3313 ms 189252 KB
sub1_56.txt 3313 ms 183376 KB
sub1_57.txt 3313 ms 181356 KB
sub1_58.txt 3313 ms 185572 KB
sub1_59.txt 3313 ms 186888 KB
sub1_60.txt 3313 ms 177388 KB
sub1_61.txt 3312 ms 145632 KB
sub1_62.txt 3312 ms 171708 KB
sub1_63.txt 73 ms 22852 KB
sub1_64.txt 3312 ms 183232 KB
sub1_65.txt 408 ms 70920 KB
sub1_66.txt 3312 ms 139140 KB
sub1_67.txt 1266 ms 126504 KB
sub1_68.txt 3312 ms 168148 KB
sub1_69.txt 3312 ms 176016 KB
sub1_70.txt 3312 ms 174152 KB
sub1_71.txt 54 ms 14324 KB
sub1_72.txt 54 ms 14340 KB
sub1_73.txt 55 ms 14392 KB
sub1_74.txt 232 ms 27928 KB
sub1_75.txt 101 ms 17684 KB
sub1_76.txt 640 ms 53800 KB
sub1_77.txt 67 ms 19652 KB
sub1_78.txt 66 ms 19728 KB
sub1_79.txt 83 ms 22900 KB
sub1_80.txt 84 ms 23196 KB
sub1_81.txt 84 ms 24184 KB
sub1_82.txt 99 ms 26460 KB
sub1_83.txt 56 ms 14468 KB
sub1_84.txt 80 ms 21080 KB
sub1_85.txt 98 ms 24068 KB
sub1_86.txt 55 ms 14448 KB
sub1_87.txt 58 ms 14288 KB
sub1_88.txt 56 ms 14400 KB
sub1_89.txt 3312 ms 170268 KB
sub1_90.txt 3312 ms 170864 KB
sub1_91.txt 3312 ms 170004 KB
sub1_92.txt 3312 ms 168424 KB
sub1_93.txt 3312 ms 169068 KB
sub1_94.txt 56 ms 14404 KB