結果

問題 No.5020 Averaging
ユーザー 寝癖寝癖
提出日時 2024-02-25 15:32:25
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 946 ms / 1,000 ms
コード長 2,525 bytes
コンパイル時間 180 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 88,020 KB
スコア 33,638,819
最終ジャッジ日時 2024-02-25 15:33:40
合計ジャッジ時間 49,995 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 941 ms
87,304 KB
testcase_01 AC 941 ms
86,524 KB
testcase_02 AC 942 ms
85,480 KB
testcase_03 AC 942 ms
85,944 KB
testcase_04 AC 942 ms
86,984 KB
testcase_05 AC 942 ms
86,796 KB
testcase_06 AC 942 ms
86,528 KB
testcase_07 AC 941 ms
88,000 KB
testcase_08 AC 941 ms
86,748 KB
testcase_09 AC 941 ms
86,244 KB
testcase_10 AC 943 ms
86,288 KB
testcase_11 AC 942 ms
86,768 KB
testcase_12 AC 941 ms
86,248 KB
testcase_13 AC 941 ms
87,184 KB
testcase_14 AC 941 ms
85,936 KB
testcase_15 AC 941 ms
87,764 KB
testcase_16 AC 941 ms
86,768 KB
testcase_17 AC 941 ms
87,524 KB
testcase_18 AC 942 ms
86,268 KB
testcase_19 AC 941 ms
86,556 KB
testcase_20 AC 941 ms
85,664 KB
testcase_21 AC 941 ms
86,096 KB
testcase_22 AC 944 ms
86,192 KB
testcase_23 AC 941 ms
86,572 KB
testcase_24 AC 943 ms
86,760 KB
testcase_25 AC 942 ms
86,896 KB
testcase_26 AC 942 ms
86,396 KB
testcase_27 AC 942 ms
86,940 KB
testcase_28 AC 942 ms
86,864 KB
testcase_29 AC 941 ms
86,588 KB
testcase_30 AC 942 ms
86,556 KB
testcase_31 AC 943 ms
86,980 KB
testcase_32 AC 942 ms
88,020 KB
testcase_33 AC 943 ms
87,376 KB
testcase_34 AC 941 ms
85,736 KB
testcase_35 AC 942 ms
86,320 KB
testcase_36 AC 946 ms
87,720 KB
testcase_37 AC 942 ms
87,716 KB
testcase_38 AC 941 ms
86,736 KB
testcase_39 AC 943 ms
86,904 KB
testcase_40 AC 944 ms
86,924 KB
testcase_41 AC 941 ms
86,504 KB
testcase_42 AC 942 ms
86,736 KB
testcase_43 AC 941 ms
87,332 KB
testcase_44 AC 942 ms
85,876 KB
testcase_45 AC 942 ms
85,564 KB
testcase_46 AC 942 ms
86,532 KB
testcase_47 AC 943 ms
85,348 KB
testcase_48 AC 941 ms
86,620 KB
testcase_49 AC 941 ms
85,852 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from math import log10, floor, exp
from random import randint, random
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 = []
A, B = init_A[:], init_B[:]
while len(op) < X//2:
    min_A, max_A = min(A), max(A)
    u, v = A.index(min_A), A.index(max_A)
    if u == v:
        break
    op.append((u+1, v+1))
    A[u], A[v] = (min_A+max_A)//2, (min_A+max_A)//2

while len(op) < X:
    min_B, max_B = min(B), max(B)
    u, v = B.index(min_B), B.index(max_B)
    if u == v:
        break
    op.append((u+1, v+1))
    B[u], B[v] = (min_B+max_B)//2, (min_B+max_B)//2

while len(op) < X:
    u, v = randint(1, N), randint(1, N)
    if u == v:
        continue
    op.append((u, v))


# 山登り法
# score = calc_socre(op)
# while time() - time_start < 0.90:
#     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]
    
# 焼きなまし
score = calc_socre(op)
start_temp = 5000
end_temp = 1
TIME_LIMIT = 0.90

while True:
    now_time = time() - time_start
    if now_time > TIME_LIMIT:
        break
    new_op = op[:]
    if randint(0, 1):
        u = randint(1, N-1)
        v = randint(u+1, N)
        new_op[randint(0, X-1)] = (u, v)
    else:
        u, v = randint(0, X-1), randint(0, X-1)
        new_op[u], new_op[v] = new_op[v], new_op[u]
    new_score = calc_socre(new_op)
    # temp = start_temp + (end_temp - start_temp) * now_time / TIME_LIMIT
    temp = start_temp * (end_temp / start_temp) ** (now_time / TIME_LIMIT)
    prob = exp(min(0, (new_score - score) / temp))
    if new_score > score or random() < prob:
        op = new_op
        score = new_score

# print(score)

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