#720915 (Crystal) No.5004 Room Assignment

提出ソース

結果

問題	No.5004 Room Assignment
ユーザー	tomerun
提出日時	2021-12-01 01:51:21
言語	Crystal (1.11.2)
結果	AC
実行時間	204 ms / 5,000 ms
コード長	2,618 bytes
コンパイル時間	15,805 ms
実行使用メモリ	22,392 KB
スコア	139,457,555
平均クエリ数	7624.05
最終ジャッジ日時	2021-12-01 01:54:29
合計ジャッジ時間	40,873 ms
ジャッジサーバーID （参考情報）	judge11 / judge14
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	177 ms 21,972 KB
testcase_01	AC	180 ms 21,948 KB
testcase_02	AC	180 ms 21,924 KB
testcase_03	AC	178 ms 22,152 KB
testcase_04	AC	177 ms 21,948 KB
testcase_05	AC	186 ms 21,924 KB
testcase_06	AC	178 ms 21,972 KB
testcase_07	AC	181 ms 22,164 KB
testcase_08	AC	180 ms 22,032 KB
testcase_09	AC	179 ms 21,936 KB
testcase_10	AC	185 ms 21,936 KB
testcase_11	AC	179 ms 21,996 KB
testcase_12	AC	179 ms 21,792 KB
testcase_13	AC	180 ms 22,152 KB
testcase_14	AC	177 ms 22,140 KB
testcase_15	AC	179 ms 21,972 KB
testcase_16	AC	179 ms 22,152 KB
testcase_17	AC	190 ms 21,936 KB
testcase_18	AC	187 ms 22,008 KB
testcase_19	AC	181 ms 21,924 KB
testcase_20	AC	178 ms 21,984 KB
testcase_21	AC	180 ms 21,936 KB
testcase_22	AC	179 ms 21,924 KB
testcase_23	AC	185 ms 21,936 KB
testcase_24	AC	200 ms 21,936 KB
testcase_25	AC	180 ms 22,104 KB
testcase_26	AC	182 ms 21,960 KB
testcase_27	AC	179 ms 22,140 KB
testcase_28	AC	181 ms 21,792 KB
testcase_29	AC	180 ms 21,972 KB
testcase_30	AC	179 ms 21,948 KB
testcase_31	AC	178 ms 22,104 KB
testcase_32	AC	182 ms 21,900 KB
testcase_33	AC	178 ms 21,948 KB
testcase_34	AC	180 ms 22,140 KB
testcase_35	AC	178 ms 22,368 KB
testcase_36	AC	179 ms 22,212 KB
testcase_37	AC	179 ms 22,068 KB
testcase_38	AC	179 ms 21,960 KB
testcase_39	AC	181 ms 22,020 KB
testcase_40	AC	202 ms 21,936 KB
testcase_41	AC	180 ms 22,140 KB
testcase_42	AC	176 ms 22,140 KB
testcase_43	AC	177 ms 22,152 KB
testcase_44	AC	180 ms 21,936 KB
testcase_45	AC	178 ms 21,968 KB
testcase_46	AC	182 ms 21,936 KB
testcase_47	AC	178 ms 21,960 KB
testcase_48	AC	192 ms 22,152 KB
testcase_49	AC	178 ms 21,924 KB
testcase_50	AC	180 ms 22,392 KB
testcase_51	AC	180 ms 22,164 KB
testcase_52	AC	180 ms 22,152 KB
testcase_53	AC	178 ms 21,792 KB
testcase_54	AC	182 ms 21,912 KB
testcase_55	AC	196 ms 22,152 KB
testcase_56	AC	204 ms 21,948 KB
testcase_57	AC	181 ms 21,960 KB
testcase_58	AC	177 ms 22,020 KB
testcase_59	AC	180 ms 22,032 KB
testcase_60	AC	177 ms 22,044 KB
testcase_61	AC	179 ms 22,104 KB
testcase_62	AC	182 ms 21,896 KB
testcase_63	AC	187 ms 21,912 KB
testcase_64	AC	181 ms 21,972 KB
testcase_65	AC	177 ms 21,936 KB
testcase_66	AC	184 ms 21,948 KB
testcase_67	AC	184 ms 21,920 KB
testcase_68	AC	181 ms 21,936 KB
testcase_69	AC	180 ms 21,912 KB
testcase_70	AC	176 ms 21,936 KB
testcase_71	AC	180 ms 21,948 KB
testcase_72	AC	187 ms 21,912 KB
testcase_73	AC	182 ms 22,152 KB
testcase_74	AC	184 ms 21,960 KB
testcase_75	AC	187 ms 21,936 KB
testcase_76	AC	181 ms 21,960 KB
testcase_77	AC	178 ms 21,912 KB
testcase_78	AC	186 ms 21,792 KB
testcase_79	AC	176 ms 22,008 KB
testcase_80	AC	178 ms 22,352 KB
testcase_81	AC	177 ms 21,972 KB
testcase_82	AC	179 ms 22,032 KB
testcase_83	AC	178 ms 21,948 KB
testcase_84	AC	180 ms 21,936 KB
testcase_85	AC	182 ms 22,164 KB
testcase_86	AC	182 ms 21,912 KB
testcase_87	AC	179 ms 21,972 KB
testcase_88	AC	178 ms 21,780 KB
testcase_89	AC	177 ms 21,924 KB
testcase_90	AC	176 ms 21,804 KB
testcase_91	AC	181 ms 21,984 KB
testcase_92	AC	178 ms 21,972 KB
testcase_93	AC	180 ms 21,768 KB
testcase_94	AC	180 ms 22,152 KB
testcase_95	AC	177 ms 21,912 KB
testcase_96	AC	179 ms 21,792 KB
testcase_97	AC	180 ms 21,972 KB
testcase_98	AC	177 ms 21,936 KB
testcase_99	AC	183 ms 21,936 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

yukicoder

結果

テストケース

ソースコード