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.map &:to_i } $rows = board $cols = board.transpose 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.map{|c| sum += c } (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.map{|c| sum += c } (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 (pos...pos+l).each{|j| $rows[idx][j] ^= 1 $cols[j][idx] ^= 1 } a = c = idx + 1 b = pos + 1 d = pos + l else (pos...pos+l).each{|j| $cols[idx][j] ^= 1 $rows[j][idx] ^= 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