結果
問題 | No.1775 Love Triangle 2 |
ユーザー |
![]() |
提出日時 | 2021-12-05 17:55:54 |
言語 | Crystal (1.14.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,211 bytes |
コンパイル時間 | 14,926 ms |
コンパイル使用メモリ | 296,060 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-07 08:38:54 |
合計ジャッジ時間 | 674,983 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 15 WA * 75 |
ソースコード
START_TIME = Time.utc.to_unix_msTL = 7500INF = 1 << 28RND = Random.new(2)INITIAL_COOLER = 0.1FINAL_COOLER = 1.0macro debug(msg){% if flag?(:local) %}STDERR.puts({{msg}}){% end %}endmaindef mainn, m = read_line.split.map(&.to_i)x, y, z = read_line.split.map { |i| i.to_i - 1 }g = Array.new(n) { [false] * n }m.times doa, b = read_line.split.map(&.to_i)g[a - 1][b - 1] = g[b - 1][a - 1] = trueendputs solve(x, y, z, g, START_TIME + TL)enddef solve(x, y, z, g, tl)n = g.sizewait = (0...n).select { |i| ![x, y, z].includes?(i) }best_ans = INFratio_pena = 1score_pena = 3ps = [x, y, z]cooler = INITIAL_COOLERturn = 0begin_time = Time.utc.to_unix_mswhile trueif (turn & 0xFFF) == 0break if best_ans == ncur_time = Time.utc.to_unix_msif cur_time > tldebug("turn: #{turn}")breakendratio = (cur_time - begin_time) / (tl - begin_time)cooler = Math.exp((1.0 - ratio) * INITIAL_COOLER + ratio * FINAL_COOLER)endpos = RND.rand(ps.size)if ps[pos] == x || ps[pos] == y || ps[pos] == zope = 1elseope = RND.rand(3)endnp = pos == ps.size - 1 ? 0 : pos + 1case opewhen 0 # removediff_pena = 0diff_pena -= 1 if g[ps[pos]][ps[np]]diff_pena -= 1 if g[ps[pos]][ps[pos - 1]]diff_pena += 1 if g[ps[pos - 1]][ps[np]]diff = diff_pena * ratio_pena - 1if accept(diff, cooler)score_pena += diff_penawait << ps[pos]ps.delete_at(pos)if score_pena == 0 && ps.size < best_ansbest_ans = ps.sizeenddebug("remove #{score_pena} #{ps.size} #{turn}")debug("#{ps}")endwhen 1 # insertnext if wait.empty?ip = RND.rand(wait.size)ins = wait[ip]diff_pena = 0diff_pena -= 1 if g[ps[pos]][ps[np]]diff_pena += 1 if g[ins][ps[np]]diff_pena += 1 if g[ins][ps[pos]]diff = diff_pena * ratio_pena + 1if accept(diff, cooler)score_pena += diff_penawait[ip], wait[-1] = wait[-1], wait[ip]wait.popps.insert(pos + 1, ins)if score_pena == 0 && ps.size < best_ansbest_ans = ps.sizeenddebug("insert #{score_pena} #{ps.size} #{turn}")debug("#{ps}")endwhen 2 # swapnext if wait.empty?ip = RND.rand(wait.size)ins = wait[ip]diff_pena = 0diff_pena -= 1 if g[ps[pos]][ps[np]]diff_pena -= 1 if g[ps[pos]][ps[pos - 1]]diff_pena += 1 if g[ins][ps[np]]diff_pena += 1 if g[ins][ps[pos - 1]]diff = diff_pena * ratio_penaif accept(diff, cooler)score_pena += diff_penawait[ip] = ps[pos]ps[pos] = insif score_pena == 0 && ps.size < best_ansbest_ans = ps.sizeenddebug("swap #{score_pena} #{ps.size} #{turn}")debug("#{ps}")endendturn += 1endreturn best_ans == INF ? -1 : best_ansenddef accept(diff, cooler)return true if diff <= 0v = -diff * coolerreturn RND.rand < Math.exp(v)end