結果
問題 | No.5020 Averaging |
ユーザー |
|
提出日時 | 2024-08-06 04:01:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 901 ms / 1,000 ms |
コード長 | 2,132 bytes |
コンパイル時間 | 471 ms |
コンパイル使用メモリ | 82,340 KB |
実行使用メモリ | 78,336 KB |
スコア | 14,082,931 |
最終ジャッジ日時 | 2024-08-06 04:02:11 |
合計ジャッジ時間 | 47,981 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
import randomimport mathfrom time import perf_counterimport sysclass TimeKeeper:def __init__(self):self.start_time = perf_counter()def is_time_over(self, LIMIT):return (perf_counter() - self.start_time) >= LIMITdef time_now(self):return (perf_counter() - self.start_time)# 定数とグローバル変数TARGET = 500000000000000000N = 0A = []B = []Order = []BestOrder = []def get_score():V1, V2 = A[0], B[0]for i in range(N - 1):V1 = (V1 + A[Order[i]]) // 2V2 = (V2 + B[Order[i]]) // 2return max(abs(TARGET - V1), abs(TARGET - V2))def main():global N, A, B, Order, BestOrdertk = TimeKeeper()LIMIT = 0.85N = int(input())A = [0] * (N + 1)B = [0] * (N + 1)for i in range(1, N + 1):A[i], B[i] = map(int, input().split())# 初期化Order = list(range(1, N))current_score = get_score()best_score = current_score# 焼きなましloop = 0T0, T1 = 0.2, 0.2T = T0while True:loop += 1if loop % 1000 == 0:T = T0 + (T1 - T0) * tk.time_now() / LIMITif tk.is_time_over(LIMIT):breakidx1 = random.randint(0, N - 2)idx2 = random.randint(0, N - 2)Order[idx1], Order[idx2] = Order[idx2], Order[idx1]cand_score = get_score() # 変更候補diff = math.log10(current_score) - math.log10(cand_score) # diff > 0:改善if random.random() < math.exp(diff / T):# 採用if best_score > cand_score:best_score = cand_scoreBestOrder = Order[:]current_score = cand_scoreelse:# 不採用の場合は元に戻すOrder[idx1], Order[idx2] = Order[idx2], Order[idx1]ANS = [(1, BestOrder[i]+1) for i in range(N - 1)]print(len(ANS))for a in ANS:print(a[0], a[1])sc = int(2*10**6 - 10**5 * math.log10(best_score + 1))print(sc, best_score, loop, file=sys.stderr)if __name__ == "__main__":main()