結果

問題 No.5020 Averaging
ユーザー 寝癖寝癖
提出日時 2024-02-25 13:22:47
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 948 ms / 1,000 ms
コード長 1,275 bytes
コンパイル時間 298 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 85,560 KB
スコア 14,020,827
最終ジャッジ日時 2024-02-25 13:23:38
合計ジャッジ時間 50,251 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 943 ms
84,004 KB
testcase_01 AC 941 ms
84,380 KB
testcase_02 AC 942 ms
83,104 KB
testcase_03 AC 940 ms
83,752 KB
testcase_04 AC 941 ms
83,368 KB
testcase_05 AC 942 ms
85,400 KB
testcase_06 AC 940 ms
83,972 KB
testcase_07 AC 944 ms
83,620 KB
testcase_08 AC 944 ms
84,012 KB
testcase_09 AC 940 ms
84,640 KB
testcase_10 AC 940 ms
83,752 KB
testcase_11 AC 941 ms
83,616 KB
testcase_12 AC 941 ms
84,504 KB
testcase_13 AC 940 ms
84,012 KB
testcase_14 AC 940 ms
83,508 KB
testcase_15 AC 941 ms
83,372 KB
testcase_16 AC 940 ms
83,836 KB
testcase_17 AC 940 ms
83,732 KB
testcase_18 AC 938 ms
83,876 KB
testcase_19 AC 941 ms
84,276 KB
testcase_20 AC 940 ms
84,260 KB
testcase_21 AC 939 ms
84,000 KB
testcase_22 AC 940 ms
83,264 KB
testcase_23 AC 939 ms
82,732 KB
testcase_24 AC 940 ms
85,052 KB
testcase_25 AC 940 ms
84,136 KB
testcase_26 AC 940 ms
84,528 KB
testcase_27 AC 940 ms
83,368 KB
testcase_28 AC 940 ms
85,560 KB
testcase_29 AC 939 ms
82,992 KB
testcase_30 AC 940 ms
84,164 KB
testcase_31 AC 940 ms
83,776 KB
testcase_32 AC 940 ms
83,880 KB
testcase_33 AC 940 ms
83,912 KB
testcase_34 AC 944 ms
83,612 KB
testcase_35 AC 939 ms
83,240 KB
testcase_36 AC 940 ms
83,364 KB
testcase_37 AC 948 ms
82,344 KB
testcase_38 AC 941 ms
83,996 KB
testcase_39 AC 939 ms
84,952 KB
testcase_40 AC 940 ms
83,120 KB
testcase_41 AC 940 ms
83,628 KB
testcase_42 AC 944 ms
84,264 KB
testcase_43 AC 940 ms
84,004 KB
testcase_44 AC 941 ms
84,280 KB
testcase_45 AC 942 ms
84,000 KB
testcase_46 AC 941 ms
83,492 KB
testcase_47 AC 942 ms
84,580 KB
testcase_48 AC 940 ms
83,244 KB
testcase_49 AC 939 ms
83,492 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from math import log10, floor
from random import randint
from time import time

time_start = time()

N = int(input())
init_A, init_B = [list(i) for i in zip(*[list(map(int, input().split())) for _ in range(N)])]

def calc_socre(op):
    A, B = exec_op(op)
    X = len(op)

    V1, V2 = abs(5*10**17-A[0]), abs(5*10**17-B[0])
    V = max(V1, V2)
    if V == 0:
        return 2000050 - X
    else:
        return floor(2000000.0 - 100000.0 * log10(V+1))

def exec_op(op):
    A, B = init_A[:], init_B[:]
    for u, v in op:
        a, b = A[u-1], A[v-1]
        A[u-1], A[v-1] = (a+b)//2, (a+b)//2
        c, d = B[u-1], B[v-1]
        B[u-1], B[v-1] = (c+d)//2, (c+d)//2
    return A, B

X = 50
op = []
for _ in range(X):
    u = randint(1, N-1)
    v = randint(u+1, N)
    op.append((u, v))

# 山登り法
score = calc_socre(op)
while time() - time_start < 0.90:
    # 確率0.5で一点変異
    if randint(0, 1):
        u = randint(1, N-1)
        v = randint(u+1, N)
        op[randint(0, X-1)] = (u, v)
    else:
        u, v = randint(0, X-1), randint(0, X-1)
        op[u], op[v] = op[v], op[u]
    new_score = calc_socre(op)
    if new_score > score:
        score = new_score
    else:
        op[u], op[v] = op[v], op[u]

print(X)
for u, v in op:
    print(u, v)
0