結果
問題 | No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance |
ユーザー |
![]() |
提出日時 | 2022-10-14 23:07:36 |
言語 | Crystal (1.14.0) |
結果 |
AC
|
実行時間 | 1,918 ms / 2,000 ms |
コード長 | 3,567 bytes |
コンパイル時間 | 17,168 ms |
実行使用メモリ | 6,952 KB |
スコア | 1,034,744,975,720,968 |
最終ジャッジ日時 | 2022-10-14 23:09:42 |
合計ジャッジ時間 | 122,104 ms |
ジャッジサーバーID (参考情報) |
judge10 / judge12 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
START_TIME = Time.utc.to_unix_msTL = 1900N = 50K = 50RND = Random.new(2)macro debug(msg){% if flag?(:local) %}STDERR.puts({{msg}}){% end %}endclass Resultgetter :score, :b, :m, :edef initialize(@score : Int64, @b : Array(Int32), @m : Array(Int32), @e : Array(Int32))endendclass Solver@ts : Array(Int32)@us : Array(Int32)def initializeread_line@ts = read_line.split.map(&.to_i)@us = read_line.split.map(&.to_i)@b = Array(Int32).new(N) { RND.rand(1) + 1 }@m = Array(Int32).new(N) { |i| {RND.rand(2) + 1, @b[i]}.min }@e = Array(Int32).new(N) { RND.rand(2) + 1 }@pos_200 = Array(Int32).new(N, 0)@dir_200 = Array(Int32).new(N, 1)N.times do |i|@pos_200[i], @dir_200[i] = sim_200(@b[i], @m[i], @e[i])end@pos_ts = Array(Array(Int32)).new(N) { Array.new(K, 0) }@pos_us = Array(Array(Int32)).new(N) { Array.new(K, 0) }N.times do |i|sim_k(i)endenddef sim_200(b, m, e)m = {b, m}.minp = 0d = 1a = b200.times dop += dif p == a * dd *= -1a = {m, a - e}.maxendendreturn p, denddef sim_k(i)K.times do |j|t = (@ts[j] - 200) % (@m[i] * 4)p = @pos_200[i]d = @dir_200[i]t.times dop += dif p == @m[i] * dd *= -1endend@pos_ts[i][j] = pt = (@us[j] - 200) % (@m[i] * 4)p = @pos_200[i]d = @dir_200[i]t.times dop += dif p == @m[i] * dd *= -1endend@pos_us[i][j] = pendenddef solvebest_res = Result.new(calc_score(), @b.dup, @m.dup, @e.dup)buf_pos_ts = Array.new(K, 0)buf_pos_us = Array.new(K, 0)turn = 0while trueturn += 1if (turn & 0x3F) == 0if Time.utc.to_unix_ms - START_TIME > TLdebug("total_turn:#{turn} score:#{best_res.score}")breakendendch_i = RND.rand(N)nb = RND.rand(13) + 1nm = {RND.rand(13) + 1, nb}.minne = RND.rand(2) + 1old = {@pos_200[ch_i], @dir_200[ch_i]}@pos_200[ch_i], @dir_200[ch_i] = sim_200(nb, nm, ne)K.times do |i|buf_pos_ts[i] = @pos_ts[ch_i][i]buf_pos_us[i] = @pos_us[ch_i][i]endsim_k(ch_i)score = calc_score()if best_res.score < scoredebug("score:#{score} at turn #{turn}")@b[ch_i] = nb@m[ch_i] = nm@e[ch_i] = nebest_res = Result.new(score, @b.dup, @m.dup, @e.dup)else@pos_200[ch_i] = old[0]@dir_200[ch_i] = old[1]K.times do |i|@pos_ts[ch_i][i] = buf_pos_ts[i]@pos_us[ch_i][i] = buf_pos_us[i]endendendreturn best_resenddef calc_scoresum0 = 0i64sum1 = 0i64K.times do |i|sum = 0.0N.times do |j|j.times do |k|sum += (@pos_ts[j][i] - @pos_ts[k][i]).abs / (@b[j] + @b[k])endendsum0 += (sum * 20_000_000 / (N * (N - 1))).round.to_imin = 1 << 20max = -(1 << 20)N.times do |j|min = {min, @pos_us[j][i]}.minmax = {max, @pos_us[j][i]}.maxendsum1 += (10_000_000 / (((max - min) * 0.05) ** 0.5 + 1)).round.to_ienddebug([sum0, sum1, sum0 * sum1])return sum0 * sum1endendsolver = Solver.newres = solver.solveN.times do |i|puts "#{res.b[i]} #{{res.b[i], res.m[i]}.min} #{res.e[i]}"end