結果

問題 No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance
ユーザー 👑 KazunKazun
提出日時 2022-10-14 22:45:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,923 ms / 2,000 ms
コード長 3,837 bytes
コンパイル時間 421 ms
実行使用メモリ 87,628 KB
スコア 1,098,968,426,077,157
最終ジャッジ日時 2022-10-14 22:47:02
合計ジャッジ時間 106,693 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,922 ms
86,276 KB
testcase_01 AC 1,918 ms
86,016 KB
testcase_02 AC 1,920 ms
86,336 KB
testcase_03 AC 1,921 ms
86,600 KB
testcase_04 AC 1,922 ms
86,172 KB
testcase_05 AC 1,918 ms
86,940 KB
testcase_06 AC 1,922 ms
86,392 KB
testcase_07 AC 1,917 ms
87,288 KB
testcase_08 AC 1,918 ms
86,044 KB
testcase_09 AC 1,919 ms
87,068 KB
testcase_10 AC 1,918 ms
86,496 KB
testcase_11 AC 1,919 ms
86,812 KB
testcase_12 AC 1,921 ms
86,292 KB
testcase_13 AC 1,918 ms
86,048 KB
testcase_14 AC 1,921 ms
85,996 KB
testcase_15 AC 1,923 ms
87,628 KB
testcase_16 AC 1,920 ms
86,484 KB
testcase_17 AC 1,921 ms
86,164 KB
testcase_18 AC 1,919 ms
86,968 KB
testcase_19 AC 1,920 ms
86,316 KB
testcase_20 AC 1,918 ms
86,892 KB
testcase_21 AC 1,919 ms
86,620 KB
testcase_22 AC 1,920 ms
86,752 KB
testcase_23 AC 1,921 ms
85,920 KB
testcase_24 AC 1,921 ms
85,900 KB
testcase_25 AC 1,919 ms
86,680 KB
testcase_26 AC 1,919 ms
86,404 KB
testcase_27 AC 1,919 ms
86,856 KB
testcase_28 AC 1,923 ms
86,196 KB
testcase_29 AC 1,919 ms
86,784 KB
testcase_30 AC 1,919 ms
86,828 KB
testcase_31 AC 1,918 ms
86,400 KB
testcase_32 AC 1,918 ms
86,412 KB
testcase_33 AC 1,920 ms
86,352 KB
testcase_34 AC 1,920 ms
86,936 KB
testcase_35 AC 1,920 ms
86,188 KB
testcase_36 AC 1,918 ms
85,684 KB
testcase_37 AC 1,921 ms
86,476 KB
testcase_38 AC 1,919 ms
86,468 KB
testcase_39 AC 1,921 ms
86,684 KB
testcase_40 AC 1,920 ms
86,092 KB
testcase_41 AC 1,919 ms
86,312 KB
testcase_42 AC 1,917 ms
86,408 KB
testcase_43 AC 1,919 ms
86,416 KB
testcase_44 AC 1,919 ms
86,360 KB
testcase_45 AC 1,921 ms
86,132 KB
testcase_46 AC 1,921 ms
86,228 KB
testcase_47 AC 1,920 ms
87,256 KB
testcase_48 AC 1,921 ms
86,936 KB
testcase_49 AC 1,920 ms
86,584 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#==================================================
# 関数部

def General_Binary_Increase_Search_Integer(L, R, cond, default=None):
    """ 条件式が単調増加であるとき, 整数上で二部探索を行う.

    L: 解の下限
    R: 解の上限
    cond: 条件(1変数関数, 広義単調増加を満たす)
    default: Lで条件を満たさないときの返り値
    """

    if not(cond(R)):
        return default

    if cond(L):
        return L

    R+=1
    while R-L>1:
        C=L+(R-L)//2
        if cond(C):
            R=C
        else:
            L=C
    return R

def move(start,direction,time):
    return start+direction*time

def position(B,M,E,T):
    if E==0:
        M=B
        E=1

    H=(B-M)//E
    F=2*B*H-E*H*H

    if T<B:
        return T

    T-=B
    if T<F:
        check=lambda p:T<2*p*B-p*p*E
        p=General_Binary_Increase_Search_Integer(1,H,check,None)

        direction=pow(-1,p)
        start=pow(-1,p-1)*(B-(p-1)*E)
        return move(start,direction,T-(2*(p-1)*B-pow(p-1,2)*E))

    T-=F
    if T<(B-H*E)+M:
        direction=pow(-1,H+1)
        start=pow(-1,H)*(B-H*E)
        return move(start,direction,T)

    if M>0:
        T-=(B-H*E)+M
        q,r=divmod(T,2*M)

        direction=pow(-1,H+2+q)
        start=pow(-1,H+1+q)*M
        return move(start,direction,r)
    else:
        return 0

def score_confrontation(B,M,E,mode=False):
    X=[[0]*N for _ in range(K)]

    C1=0
    coef=(2*pow(10,7))/(N*(N-1))
    for j in range(K):
        for i in range(N):
            X[j][i]=position(B[i], M[i], E[i], T[j])

        R=0
        for i in range(N):
            for k in range(i+1, N):
                R+=abs(X[j][i]-X[j][k])/(B[i]+B[k])
        C1+=round(coef*R)
    C=round(C1/N)

    if mode:
        return C, X
    else:
        return C

def score_cooperation(B,M,E,mode=False):
    Y=[[0]*N for _ in range(K)]

    C2=0
    for j in range(K):
        for i in range(N):
            Y[j][i]=position(B[i],M[i],E[i],U[j])
        R=max(Y[j])-min(Y[j])
        C2+=round(pow(10,7)/sqrt(R/20+1))
    C=round(C2/N)

    if mode:
        return C,Y
    else:
        return C

def calculate(B,M,E):
    C1=score_confrontation(B,M,E)
    C2=score_cooperation(B,M,E)
    return C1*C2

def scoring(X,Y):
    C1=0
    for j in range(K):
        R=0
        for i in range(N):
            for k in range(i+1,N):
                R+=abs(X[j][i]-X[j][k])/(B[i]+B[k])
        C1+=round((2*pow(10,7))/(N*(N-1))*R)
    C1=round(C1/N)

    C2=0
    for j in range(N):
        R=max(Y[j])-min(Y[j])
        C2+=round(pow(10,7)/sqrt(R/20+1))
    C2=round(C2/N)

    return C1*C2

def debug(*message):
    print(*message,file=sys.stderr)

#==================================================
# インポート
from time import *
from math import sqrt
from random import *
import sys

#==================================================
# 入力
N,K=map(int,input().split())
T=list(map(int,input().split()))
U=list(map(int,input().split()))

#==================================================
BEGIN_TIME=time()
TIME_LIMIT_A=1.800

#==================================================
# 初期解

best_score=-1
E=[1]*N
B=[1]*N

while time()-BEGIN_TIME<TIME_LIMIT_A:
    for i in range(N):
        rand=random()
        if rand<=0.46:
            B[i]=1
        elif rand<=0.92:
            B[i]=2
        elif rand<=0.96:
            B[i]=3
        else:
            B[i]=4

    M=[randint(1,B[i]) for i in range(N)]

    score=calculate(B,M,E)
    if best_score<score:
        best_score=score
        Best_B=B.copy()
        Best_M=M.copy()

#==================================================
for b,m,e in zip(Best_B,Best_M,E):
    print(b,m,e)

debug("Confrontation")
debug(score_confrontation(B,M,E))
debug("Cooperation")
debug(score_cooperation(B,M,E))

debug(best_score)
0