START_TIME = Time.utc.to_unix_ms TL = 2900 INF = 1 << 29 T = 3600 macro debug(msg) {% if flag?(:local) %} STDERR.puts({{msg}}) {% end %} end macro debugf(format_string, *args) {% if flag?(:local) %} STDERR.printf({{format_string}}, {{*args}}) {% end %} end main def main read_line solver = Solver.new(START_TIME + TL) solver.solve end class Room getter :ps, :ts, :is, :tsum def initialize @ps = [] of Int32 @ts = [] of Int32 @is = [] of Int32 @tsum = 0 end def add(s, t, id) @ps << s @ts.each { |et| @tsum += (et - t).abs } @ts << t @is << id end def pop @ps.pop @is.pop t = @ts.pop @ts.each { |et| @tsum -= (et - t).abs } end def max @ps.max end def min @ps.min end def size @ps.size end def score case @ps.size when 1 0 when 2 {(200 - (max - min) ** 2) - @tsum, 0}.max when 3 {3 * (200 - (max - min) ** 2) - @tsum, 0}.max when 4 {6 * (200 - (max - min) ** 2) - @tsum, 0}.max else -INF end end end class Solver def initialize(@timelimit : Int64) @turn = 0 @num_p = 0 @rooms = [] of Room end def solve T.times do |i| @turn = i ss = read_line.split.map(&.to_i) n = ss.shift merge = [] of Tuple(Int32, Int32) ss.each do |s| @num_p += 1 len = range(s) best_diff = 0 best_room = nil @rooms.each do |r| next if r.size == 4 next if r.min < s - len || s + len < r.max diff = -r.score r.add(s, @turn, @num_p) diff += r.score r.pop if diff > best_diff best_diff = diff best_room = r end end if best_room best_room.add(s, @turn, @num_p) merge << {best_room.is[0], @num_p} else r = Room.new r.add(s, @turn, @num_p) @rooms << r end end puts merge.size merge.each do |m| puts "#{m[0]} #{m[1]}" end STDOUT.flush end # @rooms.each do |r| # debug("#{r.size} #{r.ps} #{r.ts} #{r.score}") # end score = @rooms.map { |r| r.score }.sum debug("score:#{score}") end def range(s) d = (s - 50).abs if d <= 0 return 1 elsif d <= 4 return 2 elsif d <= 12 return 3 elsif d <= 25 return 4 elsif d <= 35 return 5 elsif d <= 45 return 6 else return 10 end end end