結果

問題 No.5020 Averaging
ユーザー tomerun
提出日時 2024-02-25 14:24:02
言語 Crystal
(1.14.0)
結果
AC  
実行時間 904 ms / 1,000 ms
コード長 4,636 bytes
コンパイル時間 15,650 ms
コンパイル使用メモリ 292,236 KB
実行使用メモリ 6,676 KB
スコア 24,837,840
最終ジャッジ日時 2024-02-25 14:25:06
合計ジャッジ時間 64,119 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

START_TIME = Time.utc.to_unix_ms
TL         = (ENV["TL"]? || 900).to_i
PART       = (ENV["PART"]? || 100).to_i
IC         = (ENV["IC"]? || 1).to_f
FC         = (ENV["FC"]? || 50).to_f
N          = 45
INF        = 1u64 << 62
MED        = 500_000_000_000_000_000i64
RND        = Random.new(2)
alias PI = Tuple(Int32, Int32)
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
def crash(msg, caller_line = __LINE__)
  puts "[ERROR] line #{caller_line}: #{msg}"
  exit
end
macro assert(cond, msg = "", caller_line = __LINE__)
  {% if flag?(:local) %}
    if !({{cond}})
      crash({{msg}}, {{caller_line}})
    end
  {% end %}
end
record Pos, y : Int32, x : Int32
class Result
  property :pairs, :v0, :v1
  getter :score
  @score : Float64
  def initialize(@pairs : Array(PI), @v0 : Int64, @v1 : Int64)
    @score = Math.log10({(@v0 - MED).abs, (@v1 - MED).abs}.max + 1)
  end
  def to_s(io)
    io << "#{@pairs.size}\n" << @pairs.map { |p| {p[0] + 1, p[1] + 1}.join(" ") }.join("\n")
  end
end
RES_EMPTY = Result.new([] of PI, 0u64, 0u64)
def dist(y0, x0, y1, x1)
  return (y0 - y1).abs + (x0 - x1).abs
end
def dist(p0, p1)
  return (p0.y - p1.y).abs + (p0.x - p1.x).abs
end
STATE_EMPTY = State.new([INF], 0, [] of Int32, nil, INF)
class Solver
  def initialize(@a : Array(Int64), @b : Array(Int64))
  end
  def solve(timelimit)
    av = @a.map { |v| v >> 6 }
    bv = @b.map { |v| v >> 6 }
    is = N.times.to_a
    N.times do |i|
      is.swap(i, RND.rand(N - i) + i)
    end
    on = is.first(19)
    off = is.last(N - on.size)
    med = MED
    sum_a = av.sum + on.map { |i| av[i] }.sum
    sum_b = bv.sum + on.map { |i| bv[i] }.sum
    cost = (sum_a - med).to_f ** 2 + (sum_b - med).to_f ** 2
    best_cost = cost
    best_on = on.dup
    debug("initial_cost:#{cost}")
    turn = 0
    cooler = IC
    init_time = Time.utc.to_unix_ms
    while true
      turn += 1
      if (turn & 0xFFF) == 0
        cur_time = Time.utc.to_unix_ms
        if cur_time > timelimit
          debug("turn:#{turn}\n")
          break
        end
        ratio = (cur_time - init_time) / (timelimit - init_time)
        cooler = (1.0 - ratio) * IC + ratio * FC
      end
      on_i = RND.rand(on.size)
      off_i = RND.rand(off.size)
      v0 = on[on_i]
      v1 = off[off_i]
      na = sum_a - av[v0] + av[v1]
      nb = sum_b - bv[v0] + bv[v1]
      nc = (na - med).to_f ** 2 + (nb - med).to_f ** 2
      if (accept(nc, cost, cooler))
        cost = nc
        on[on_i] = v1
        off[off_i] = v0
        sum_a = na
        sum_b = nb
        if nc < best_cost
          debug("best_cost:#{nc} turn:#{turn} diff_a:#{sum_a - med} diff_b:#{sum_b - med}")
          best_cost = nc
          best_on = on.dup
        end
      end
    end
    best_off = N.times.reject { |i| best_on.includes?(i) }.to_a
    ans = [] of PI
    la = @a.dup
    lb = @b.dup
    (best_off.size // 2).times do |i|
      i0 = best_off[i * 2]
      i1 = best_off[i * 2 + 1]
      ans << {i0, i1}
      best_on << {i0, i1}.min
      sa = (la[i0] + la[i1]) // 2
      sb = (lb[i0] + lb[i1]) // 2
      la[i0] = la[i1] = sa
      lb[i0] = lb[i1] = sb
    end
    while best_on.size > 1
      i0 = best_on.shift
      i1 = best_on.shift
      ans << {i0, i1}
      best_on << {i0, i1}.min
      sa = (la[i0] + la[i1]) // 2
      sb = (lb[i0] + lb[i1]) // 2
      la[i0] = la[i1] = sa
      lb[i0] = lb[i1] = sb
    end
    return Result.new(ans, la[0], lb[0])
  end
  def accept(new_cost, old_cost, cooler)
    return true if new_cost <= old_cost
    diff = new_cost - old_cost
    v = -diff / old_cost * cooler
    # debug(v)
    return false if v < -8
    return RND.rand < Math.exp(v)
  end
end
def main
  gets
  a = [] of Int64
  b = [] of Int64
  N.times do |i|
    u, v = read_line.split.map(&.to_i64)
    a << u
    b << v
  end
  solver = Solver.new(a, b)
  best_res = Result.new([] of PI, a[0], b[0])
  # turn = 0
  # while Time.utc.to_unix_ms - START_TIME < TL
  #   res = solver.solve(START_TIME + TL)
  #   if res.cost < best_res.cost
  #     debug("best_cost:#{res.cost} at turn:#{turn}")
  #     best_res = res
  #   end
  #   turn += 1
  # end
  # debug("turn:#{turn}")
  part = PART
  part.times do |i|
    res = solver.solve(START_TIME + TL * (i + 1) // part)
    if res.score < best_res.score
      best_res = res
    end
  end
  puts best_res
  {% if flag?(:local) %}
    STDERR.printf("raw:%7f score:%d\n", best_res.score, (2000000 - 100000 * best_res.score).floor)
  {% end %}
end
main
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0