結果

問題 No.5004 Room Assignment
ユーザー tomeruntomerun
提出日時 2021-12-01 00:39:09
言語 Crystal
(1.11.2)
結果
AC  
実行時間 201 ms / 5,000 ms
コード長 2,569 bytes
コンパイル時間 18,651 ms
実行使用メモリ 22,368 KB
スコア 138,632,287
平均クエリ数 7636.82
最終ジャッジ日時 2021-12-01 00:39:52
合計ジャッジ時間 41,128 ms
ジャッジサーバーID
(参考情報)
judge12 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 178 ms
21,980 KB
testcase_01 AC 177 ms
21,936 KB
testcase_02 AC 176 ms
21,972 KB
testcase_03 AC 179 ms
22,032 KB
testcase_04 AC 175 ms
21,768 KB
testcase_05 AC 175 ms
21,900 KB
testcase_06 AC 177 ms
22,104 KB
testcase_07 AC 178 ms
21,876 KB
testcase_08 AC 201 ms
21,948 KB
testcase_09 AC 177 ms
21,732 KB
testcase_10 AC 176 ms
22,104 KB
testcase_11 AC 174 ms
21,900 KB
testcase_12 AC 183 ms
21,936 KB
testcase_13 AC 175 ms
21,948 KB
testcase_14 AC 176 ms
21,924 KB
testcase_15 AC 175 ms
21,936 KB
testcase_16 AC 182 ms
21,912 KB
testcase_17 AC 180 ms
21,924 KB
testcase_18 AC 183 ms
21,960 KB
testcase_19 AC 174 ms
21,996 KB
testcase_20 AC 174 ms
21,936 KB
testcase_21 AC 178 ms
22,200 KB
testcase_22 AC 176 ms
22,140 KB
testcase_23 AC 199 ms
21,960 KB
testcase_24 AC 176 ms
21,948 KB
testcase_25 AC 177 ms
21,792 KB
testcase_26 AC 177 ms
21,792 KB
testcase_27 AC 176 ms
22,032 KB
testcase_28 AC 178 ms
21,948 KB
testcase_29 AC 179 ms
21,936 KB
testcase_30 AC 180 ms
21,912 KB
testcase_31 AC 178 ms
21,924 KB
testcase_32 AC 175 ms
21,936 KB
testcase_33 AC 176 ms
22,368 KB
testcase_34 AC 176 ms
21,804 KB
testcase_35 AC 174 ms
21,948 KB
testcase_36 AC 175 ms
21,948 KB
testcase_37 AC 176 ms
22,140 KB
testcase_38 AC 182 ms
21,900 KB
testcase_39 AC 181 ms
21,612 KB
testcase_40 AC 176 ms
21,936 KB
testcase_41 AC 175 ms
22,044 KB
testcase_42 AC 175 ms
21,912 KB
testcase_43 AC 175 ms
21,948 KB
testcase_44 AC 174 ms
21,932 KB
testcase_45 AC 177 ms
21,924 KB
testcase_46 AC 180 ms
21,912 KB
testcase_47 AC 181 ms
22,092 KB
testcase_48 AC 179 ms
21,948 KB
testcase_49 AC 177 ms
21,780 KB
testcase_50 AC 175 ms
21,984 KB
testcase_51 AC 175 ms
21,924 KB
testcase_52 AC 176 ms
21,912 KB
testcase_53 AC 177 ms
21,780 KB
testcase_54 AC 180 ms
21,948 KB
testcase_55 AC 180 ms
21,948 KB
testcase_56 AC 176 ms
22,140 KB
testcase_57 AC 176 ms
22,116 KB
testcase_58 AC 177 ms
21,912 KB
testcase_59 AC 177 ms
22,116 KB
testcase_60 AC 175 ms
21,948 KB
testcase_61 AC 180 ms
21,948 KB
testcase_62 AC 183 ms
22,104 KB
testcase_63 AC 179 ms
21,912 KB
testcase_64 AC 178 ms
21,912 KB
testcase_65 AC 176 ms
22,020 KB
testcase_66 AC 177 ms
22,152 KB
testcase_67 AC 175 ms
22,200 KB
testcase_68 AC 176 ms
21,804 KB
testcase_69 AC 176 ms
22,164 KB
testcase_70 AC 178 ms
22,068 KB
testcase_71 AC 178 ms
21,968 KB
testcase_72 AC 175 ms
22,068 KB
testcase_73 AC 175 ms
21,948 KB
testcase_74 AC 174 ms
21,924 KB
testcase_75 AC 176 ms
21,924 KB
testcase_76 AC 176 ms
22,020 KB
testcase_77 AC 176 ms
21,912 KB
testcase_78 AC 181 ms
21,864 KB
testcase_79 AC 179 ms
21,924 KB
testcase_80 AC 177 ms
22,116 KB
testcase_81 AC 176 ms
21,936 KB
testcase_82 AC 174 ms
21,924 KB
testcase_83 AC 176 ms
21,936 KB
testcase_84 AC 177 ms
21,948 KB
testcase_85 AC 177 ms
22,356 KB
testcase_86 AC 182 ms
21,960 KB
testcase_87 AC 176 ms
21,768 KB
testcase_88 AC 175 ms
21,932 KB
testcase_89 AC 177 ms
21,960 KB
testcase_90 AC 175 ms
22,104 KB
testcase_91 AC 175 ms
21,948 KB
testcase_92 AC 175 ms
21,960 KB
testcase_93 AC 177 ms
21,816 KB
testcase_94 AC 181 ms
21,960 KB
testcase_95 AC 175 ms
21,756 KB
testcase_96 AC 174 ms
21,936 KB
testcase_97 AC 181 ms
21,936 KB
testcase_98 AC 178 ms
22,356 KB
testcase_99 AC 178 ms
21,900 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

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
0