#720917 (Crystal) No.5004 Room Assignment

• 問題: No.5004 Room Assignment
• ユーザー: tomerun
• 提出日時: 2021-12-01 01:59:31
• 言語: Crystal (1.11.2)
• 結果: AC
• 実行時間: 183 ms / 5,000 ms
• コード長: 2,620 bytes
• コンパイル時間: 16,861 ms
• 実行使用メモリ: 22,404 KB
• スコア: 139,568,008
• 平均クエリ数: 7624.29
• 最終ジャッジ日時: 2021-12-01 02:00:12
• 合計ジャッジ時間: 39,820 ms
• ジャッジサーバーID （参考情報）: judge16 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	169 ms; 21,600 KB
testcase_01	AC	171 ms; 21,924 KB
testcase_02	AC	170 ms; 21,984 KB
testcase_03	AC	177 ms; 22,140 KB
testcase_04	AC	167 ms; 21,780 KB
testcase_05	AC	167 ms; 21,960 KB
testcase_06	AC	170 ms; 21,936 KB
testcase_07	AC	170 ms; 21,960 KB
testcase_08	AC	170 ms; 21,936 KB
testcase_09	AC	169 ms; 21,960 KB
testcase_10	AC	176 ms; 21,924 KB
testcase_11	AC	174 ms; 21,948 KB
testcase_12	AC	168 ms; 21,960 KB
testcase_13	AC	170 ms; 21,972 KB
testcase_14	AC	168 ms; 21,948 KB
testcase_15	AC	169 ms; 21,900 KB
testcase_16	AC	172 ms; 22,128 KB
testcase_17	AC	181 ms; 21,960 KB
testcase_18	AC	176 ms; 22,128 KB
testcase_19	AC	178 ms; 22,152 KB
testcase_20	AC	169 ms; 22,152 KB
testcase_21	AC	171 ms; 22,128 KB
testcase_22	AC	170 ms; 21,804 KB
testcase_23	AC	172 ms; 22,032 KB
testcase_24	AC	169 ms; 21,960 KB
testcase_25	AC	173 ms; 21,960 KB
testcase_26	AC	183 ms; 21,924 KB
testcase_27	AC	174 ms; 22,080 KB
testcase_28	AC	173 ms; 21,924 KB
testcase_29	AC	173 ms; 21,924 KB
testcase_30	AC	174 ms; 22,164 KB
testcase_31	AC	172 ms; 21,984 KB
testcase_32	AC	172 ms; 21,792 KB
testcase_33	AC	175 ms; 22,128 KB
testcase_34	AC	176 ms; 22,020 KB
testcase_35	AC	178 ms; 22,164 KB
testcase_36	AC	173 ms; 21,924 KB
testcase_37	AC	173 ms; 21,780 KB
testcase_38	AC	174 ms; 21,948 KB
testcase_39	AC	174 ms; 21,912 KB
testcase_40	AC	177 ms; 21,948 KB
testcase_41	AC	170 ms; 21,924 KB
testcase_42	AC	175 ms; 21,792 KB
testcase_43	AC	173 ms; 22,092 KB
testcase_44	AC	172 ms; 22,404 KB
testcase_45	AC	175 ms; 21,792 KB
testcase_46	AC	174 ms; 21,948 KB
testcase_47	AC	174 ms; 21,948 KB
testcase_48	AC	173 ms; 21,900 KB
testcase_49	AC	171 ms; 22,092 KB
testcase_50	AC	177 ms; 22,008 KB
testcase_51	AC	176 ms; 21,960 KB
testcase_52	AC	170 ms; 22,212 KB
testcase_53	AC	172 ms; 22,140 KB
testcase_54	AC	173 ms; 21,948 KB
testcase_55	AC	174 ms; 21,912 KB
testcase_56	AC	171 ms; 22,020 KB
testcase_57	AC	175 ms; 21,912 KB
testcase_58	AC	174 ms; 22,212 KB
testcase_59	AC	177 ms; 21,948 KB
testcase_60	AC	171 ms; 22,104 KB
testcase_61	AC	172 ms; 22,008 KB
testcase_62	AC	174 ms; 21,936 KB
testcase_63	AC	171 ms; 21,792 KB
testcase_64	AC	171 ms; 22,164 KB
testcase_65	AC	172 ms; 21,960 KB
testcase_66	AC	176 ms; 22,032 KB
testcase_67	AC	177 ms; 21,948 KB
testcase_68	AC	173 ms; 21,936 KB
testcase_69	AC	176 ms; 22,212 KB
testcase_70	AC	170 ms; 22,128 KB
testcase_71	AC	170 ms; 21,960 KB
testcase_72	AC	175 ms; 21,768 KB
testcase_73	AC	170 ms; 22,104 KB
testcase_74	AC	172 ms; 21,780 KB
testcase_75	AC	177 ms; 22,380 KB
testcase_76	AC	176 ms; 21,924 KB
testcase_77	AC	172 ms; 21,984 KB
testcase_78	AC	175 ms; 22,128 KB
testcase_79	AC	171 ms; 21,948 KB
testcase_80	AC	172 ms; 21,924 KB
testcase_81	AC	171 ms; 21,780 KB
testcase_82	AC	171 ms; 21,780 KB
testcase_83	AC	169 ms; 21,932 KB
testcase_84	AC	176 ms; 22,128 KB
testcase_85	AC	174 ms; 21,924 KB
testcase_86	AC	171 ms; 21,948 KB
testcase_87	AC	172 ms; 21,912 KB
testcase_88	AC	172 ms; 21,912 KB
testcase_89	AC	170 ms; 22,212 KB
testcase_90	AC	172 ms; 22,368 KB
testcase_91	AC	174 ms; 21,912 KB
testcase_92	AC	175 ms; 21,924 KB
testcase_93	AC	176 ms; 21,912 KB
testcase_94	AC	171 ms; 22,212 KB
testcase_95	AC	173 ms; 21,924 KB
testcase_96	AC	171 ms; 22,020 KB
testcase_97	AC	175 ms; 22,140 KB
testcase_98	AC	170 ms; 21,972 KB
testcase_99	AC	172 ms; 21,936 KB

ソースコード

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 = @turn < 3600 ? 100 : 30
        best_room = nil
        @rooms.each do |r|
          next if r.size == 4
          next if (s < r.min || r.max < s) && (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 <= 3
      return 2
    elsif d <= 20
      return 3
    elsif d <= 28
      return 4
    elsif d <= 43
      return 5
    elsif d <= 45
      return 6
    else
      return 7
    end
  end
end