結果

問題 No.5004 Room Assignment
ユーザー tomerun
提出日時 2021-12-01 00:39:09
言語 Crystal
(1.14.0)
結果
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
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

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