結果
問題 | No.5020 Averaging |
ユーザー |
![]() |
提出日時 | 2024-02-25 13:31:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 889 ms / 1,000 ms |
コード長 | 1,455 bytes |
コンパイル時間 | 363 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 79,008 KB |
スコア | 34,425,630 |
最終ジャッジ日時 | 2024-02-25 13:32:36 |
合計ジャッジ時間 | 47,659 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge10 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
from time import time start_time = time() import sys import io, os input = sys.stdin.readline #input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline import math import random random.seed(42) m = 50 TIME_LIMIT = 0.85 L = 5*10**17 n = int(input()) A = [0]*n B = [0]*n for i in range(n): a, b = map(int, input().split()) A[i] = a B[i] = b ans = [] for i in range(m): u, v = random.sample(range(n), 2) ans.append((u, v)) def calc_score(ans): Ac = A.copy() Bc = B.copy() for u, v in ans: x = (Ac[u]+Ac[v])//2 Ac[u], Ac[v] = x, x y = (Bc[u]+Bc[v])//2 Bc[u], Bc[v] = y, y v1 = abs(L-Ac[0]) v2 = abs(L-Bc[0]) cost = max(v1, v2) return cost cost = calc_score(ans) iter = 0 while True: iter += 1 now_time = time() if now_time - start_time > TIME_LIMIT: break # ランダムに1操作を選んで変更する i = random.randint(0, m-1) u, v = random.sample(range(n), 2) pre = ans[i] ans[i] = (u, v) new_cost = calc_score(ans) if new_cost <= cost: cost = new_cost else: ans[i] = pre print(len(ans)) for i in range(len(ans)): u, v = ans[i] u, v = u+1, v+1 print(u, v) if cost != 0: score = (int)(2000000-100000*math.log10(cost+1)) else: score = 2000050-len(ans) print(cost, file=sys.stderr) print(round(2000000-100000*math.log(cost+1)), file=sys.stderr) print(score, file=sys.stderr)