結果

問題 No.5004 Room Assignment
ユーザー tomeruntomerun
提出日時 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
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0