#807408 (PyPy3) No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance

提出ソース

結果

問題	No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance
ユーザー	kys
提出日時	2022-10-14 23:38:34
言語	PyPy3 (7.3.15)
結果	AC
実行時間	1,887 ms / 2,000 ms
コード長	5,049 bytes
コンパイル時間	255 ms
実行使用メモリ	88,516 KB
スコア	139,460,876,471,022
最終ジャッジ日時	2022-10-14 23:40:21
合計ジャッジ時間	104,792 ms
ジャッジサーバーID （参考情報）	judge13 / judge9
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1,875 ms 87,256 KB
testcase_01	AC	1,876 ms 87,352 KB
testcase_02	AC	1,873 ms 87,296 KB
testcase_03	AC	1,873 ms 87,292 KB
testcase_04	AC	1,876 ms 87,416 KB
testcase_05	AC	1,886 ms 87,556 KB
testcase_06	AC	1,874 ms 87,888 KB
testcase_07	AC	1,876 ms 87,452 KB
testcase_08	AC	1,875 ms 87,756 KB
testcase_09	AC	1,872 ms 87,624 KB
testcase_10	AC	1,873 ms 87,572 KB
testcase_11	AC	1,873 ms 87,256 KB
testcase_12	AC	1,885 ms 87,516 KB
testcase_13	AC	1,874 ms 87,828 KB
testcase_14	AC	1,875 ms 87,520 KB
testcase_15	AC	1,875 ms 88,516 KB
testcase_16	AC	1,878 ms 87,240 KB
testcase_17	AC	1,876 ms 87,916 KB
testcase_18	AC	1,875 ms 87,484 KB
testcase_19	AC	1,876 ms 87,444 KB
testcase_20	AC	1,876 ms 87,604 KB
testcase_21	AC	1,874 ms 87,488 KB
testcase_22	AC	1,877 ms 87,692 KB
testcase_23	AC	1,874 ms 87,520 KB
testcase_24	AC	1,875 ms 87,328 KB
testcase_25	AC	1,874 ms 87,668 KB
testcase_26	AC	1,886 ms 87,548 KB
testcase_27	AC	1,875 ms 87,140 KB
testcase_28	AC	1,880 ms 87,840 KB
testcase_29	AC	1,873 ms 87,456 KB
testcase_30	AC	1,875 ms 87,584 KB
testcase_31	AC	1,872 ms 87,376 KB
testcase_32	AC	1,876 ms 87,696 KB
testcase_33	AC	1,873 ms 87,644 KB
testcase_34	AC	1,875 ms 87,364 KB
testcase_35	AC	1,886 ms 87,412 KB
testcase_36	AC	1,873 ms 87,856 KB
testcase_37	AC	1,873 ms 87,316 KB
testcase_38	AC	1,874 ms 87,532 KB
testcase_39	AC	1,876 ms 87,480 KB
testcase_40	AC	1,875 ms 87,028 KB
testcase_41	AC	1,883 ms 86,440 KB
testcase_42	AC	1,885 ms 86,896 KB
testcase_43	AC	1,878 ms 87,184 KB
testcase_44	AC	1,876 ms 87,228 KB
testcase_45	AC	1,875 ms 87,264 KB
testcase_46	AC	1,873 ms 86,512 KB
testcase_47	AC	1,887 ms 88,032 KB
testcase_48	AC	1,875 ms 86,264 KB
testcase_49	AC	1,875 ms 87,296 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

def main():
    from sys import stdin, setrecursionlimit
    # setrecursionlimit(1000000)
    input = stdin.readline
    def iinput(): return int(input())
    def sinput(): return input().rstrip()
    def i0input(): return int(input()) - 1
    def linput(): return list(input().split())
    def liinput(): return list(map(int, input().split()))
    def miinput(): return map(int, input().split())
    def li0input(): return list(map(lambda x: int(x) - 1, input().split()))
    def mi0input(): return map(lambda x: int(x) - 1, input().split())
    INF = 1000000000000000000
    MOD = 1000000007

    from itertools import combinations
    from math import sqrt, exp

    def score():
        X = [[] for _ in [0] * K]
        Y = [[] for _ in [0] * K]
        for b, m, e in zip(Bs, Ms, Es):
            start = 2 * b
            diff = 2 * e
            end = 2 * m
            last = (b - m) // e
            thr = start * (last + 1) - last * (last + 1) // 2 * diff
            for i, t in enumerate(T):
                if t <= thr:
                    ok = MAXBE
                    ng = -1
                    while ng + 1 < ok:
                        ch = (ng + ok) // 2
                        if t < start * (ch + 1) - ch * (ch + 1) // 2 * diff:
                            ng = ch
                        else:
                            ok = ch
                    t -= start * ok - ok * (ok - 1) // 2 * diff
                    if ok % 2:
                        sgn = -1
                    else:
                        sgn = 1
                    if t <= (start - ok * diff) // 2:
                        X[i].append(sgn * t)
                    else:
                        X[i].append(sgn * (start - ok * diff - t))
                else:
                    t -= start * (last + 1) - last * (last + 1) // 2 * diff
                    ok = last + t // end
                    t %= end
                    if ok % 2:
                        sgn = -1
                    else:
                        sgn = 1
                    if t <= end // 2:
                        X[i].append(sgn * t)
                    else:
                        X[i].append(sgn * (end - t))
            for i, t in enumerate(U):
                if t <= thr:
                    ok = MAXBE
                    ng = -1
                    while ng + 1 < ok:
                        ch = (ng + ok) // 2
                        if t < start * (ch + 1) - ch * (ch + 1) // 2 * diff:
                            ng = ch
                        else:
                            ok = ch
                    t -= start * ok - ok * (ok - 1) // 2 * diff
                    if ok % 2:
                        sgn = -1
                    else:
                        sgn = 1
                    if t <= (start - ok * diff) // 2:
                        Y[i].append(sgn * t)
                    else:
                        Y[i].append(sgn * (start - ok * diff - t))
                else:
                    t -= start * (last + 1) - last * (last + 1) // 2 * diff
                    ok = last + t // end
                    t %= end
                    if ok % 2:
                        sgn = -1
                    else:
                        sgn = 1
                    if t <= end // 2:
                        Y[i].append(sgn * t)
                    else:
                        Y[i].append(sgn * (end - t))
        tmp1 = []
        for x in X:
            tmp1.append(0)
            for i in range(N):
                for j in range(i+1, N):
                    tmp1[-1] += abs(x[i] - x[j]) / (Bs[i] + Bs[j])
            tmp1[-1] *= 20000000 / N / (N - 1)
        tmp2 = []
        for x in Y:
            tmp2.append(0)
            for i in range(N):
                for j in range(i+1, N):
                    tmp2[-1] = max(tmp2[-1], abs(x[i] - x[j]))
            tmp2[-1] = 10000000 / sqrt(tmp2[-1] / 20 + 1)
        ans1 = round(sum(tmp1) / K)
        ans2 = round(sum(tmp2) / K)
        return ans1 * ans2

    from random import randint, random

    N, K = miinput()
    MAXBE = 10**3
    START_TEMP = 10000000
    END_TEMP = 1000

    T = liinput()
    U = liinput()

    Bs = [randint(1, MAXBE) for _ in [0] * N]
    Ms = []
    for b in Bs:
        Ms.append(randint(1, b))
    
    Es = [randint(1, MAXBE) for _ in [0] * N]

    tmp_score = score()
    while time() - S < 1.8:
        idx = randint(0, N-1)
        newb = randint(1, MAXBE)
        newm = randint(1, newb)
        newe = randint(1, MAXBE)
        oldb = Bs[idx]
        oldm = Ms[idx]
        olde = Es[idx]
        Bs[idx], Ms[idx], Es[idx] = newb, newm, newe
        new_score = score()
        temp = START_TEMP + (END_TEMP - START_TEMP) * time() / 2
        if exp((new_score - tmp_score) / temp) < random():
            Bs[idx], Ms[idx], Es[idx] = oldb, oldm, olde
        else:
            tmp_score = new_score
            # print(tmp_score)

    for b, m, e in zip(Bs, Ms, Es):
        print(b, m, e)
    # print(score() * 50)
from time import time
S = time()

main()

yukicoder

結果

テストケース

ソースコード