DEBUG = false N, K = gets.split.map &:to_i L = gets.split.map &:to_i LI = L.map.with_index{|l, i| [l, i]}.sort_by{|l, i| -l} board = $<.map{|s| s.chomp.chars } $rows = board.map{|a| a*"" } $cols = board.transpose.map{|a| a*"" } def count_white $rows.map{|a| N - a.count(?1) }.sum end FirstScore = count_white def calc_score count_white - FirstScore end p FirstScore if DEBUG p calc_score() if DEBUG def update_memo(len) max = 0 res = nil $rows.each_with_index{|s, i| cusum = [sum = 0] + s.chars.map{|c| sum += c == ?1 ? 1 : 0 } (0..N-len).each{|j| if cusum[j+len] - cusum[j] > max max = cusum[j+len] - cusum[j] res = [:r, max, i, j] return res if max >= len end } } $cols.each_with_index{|s, i| cusum = [sum = 0] + s.chars.map{|c| sum += c == ?1 ? 1 : 0 } (0..N-len).each{|j| if cusum[j+len] - cusum[j] > max max = cusum[j+len] - cusum[j] res = [:c, max, i, j] return res if max >= len end } } res end ans = [] LI.each{|l, i| sym, size, idx, pos = update_memo(l) if sym.nil? sym = [:r, :c].sample idx = rand(N) pos = rand(N) end pos = [N - l, pos].min if sym == :r t = $rows[idx][pos, l] $rows[idx][pos, l] = t.tr("01", "10") (pos...pos+l).each{|j| c = $cols[j][idx] $cols[j][idx] = c == ?1 ? ?0 : ?1 } a = c = idx + 1 b = pos + 1 d = pos + l else t = $cols[idx][pos, l] $cols[idx][pos, l] = t.tr("01", "10") (pos...pos+l).each{|j| c = $rows[j][idx] $rows[j][idx] = c == ?1 ? ?0 : ?1 } b = d = idx + 1 a = pos + 1 c = pos + l end ans[i] = [a, b, c, d] } ans.each{|a| puts a * " " } p calc_score() if DEBUG