START_TIME = Time.utc.to_unix_ms TL = (ENV["TL"]? || 900).to_i PART = (ENV["PART"]? || 1).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 >> 10 } bv = @b.map { |v| v >> 10 } level = [1] * 2 + [2] * 3 + [4] * 8 + [8] * 9 + [16] * 9 + [32] * 8 + [64] * 4 + [128] * 2 N.times do |i| level.swap(i, RND.rand(N - i) + i) end med = MED sum_a = N.times.sum { |i| av[i] * level[i] } sum_b = N.times.sum { |i| bv[i] * level[i] } cost = (sum_a - med).to_f ** 2 + (sum_b - med).to_f ** 2 best_cost = cost best_level = level.dup debug("initial_cost:#{cost} #{sum_a} #{sum_b} #{med}") 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 v0 = RND.rand(N) v1 = RND.rand(N - 1) v1 += 1 if v1 >= v0 while level[v0] == level[v1] v0 = RND.rand(N) v1 = RND.rand(N - 1) v1 += 1 if v1 >= v0 end na = sum_a + av[v0] * (level[v1] - level[v0]) + av[v1] * (level[v0] - level[v1]) nb = sum_b + bv[v0] * (level[v1] - level[v0]) + bv[v1] * (level[v0] - level[v1]) nc = (na - med).to_f ** 2 + (nb - med).to_f ** 2 if (accept(nc, cost, cooler) || (turn & 0xFF) == 0) cost = nc level.swap(v0, v1) 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_level = level.dup end end end ords = Array.new(11) { [] of Int32 } N.times { |i| ords[best_level[i].trailing_zeros_count] << i } ans = [] of PI la = @a.dup lb = @b.dup ords.size.times do |i| ord = ords[i] debug(ord.size) while ord.size > 1 i0 = ord.pop i1 = ord.pop ans << {i0, i1} ords[i + 1] << {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 end return Result.new(ans, la[0], lb[0]) end def accept(new_cost, old_cost, cooler) return true if new_cost <= old_cost return false # diff = new_cost - old_cost # diff = Math.log10(new_cost) - Math.log10(old_cost) # v = -diff * cooler # # v = -diff / old_cost * cooler # 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