結果
問題 | No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance |
ユーザー | Kazun |
提出日時 | 2022-10-14 22:38:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,924 ms / 2,000 ms |
コード長 | 3,808 bytes |
コンパイル時間 | 240 ms |
実行使用メモリ | 87,280 KB |
スコア | 1,116,899,169,693,692 |
最終ジャッジ日時 | 2022-10-14 22:40:09 |
合計ジャッジ時間 | 105,120 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,914 ms
86,300 KB |
testcase_01 | AC | 1,908 ms
86,720 KB |
testcase_02 | AC | 1,909 ms
86,552 KB |
testcase_03 | AC | 1,910 ms
85,616 KB |
testcase_04 | AC | 1,909 ms
86,048 KB |
testcase_05 | AC | 1,912 ms
85,640 KB |
testcase_06 | AC | 1,908 ms
86,980 KB |
testcase_07 | AC | 1,909 ms
86,748 KB |
testcase_08 | AC | 1,910 ms
86,868 KB |
testcase_09 | AC | 1,910 ms
86,408 KB |
testcase_10 | AC | 1,905 ms
86,128 KB |
testcase_11 | AC | 1,909 ms
86,696 KB |
testcase_12 | AC | 1,908 ms
86,568 KB |
testcase_13 | AC | 1,909 ms
86,308 KB |
testcase_14 | AC | 1,911 ms
85,772 KB |
testcase_15 | AC | 1,910 ms
86,524 KB |
testcase_16 | AC | 1,911 ms
85,796 KB |
testcase_17 | AC | 1,911 ms
86,072 KB |
testcase_18 | AC | 1,909 ms
86,336 KB |
testcase_19 | AC | 1,910 ms
86,412 KB |
testcase_20 | AC | 1,909 ms
86,296 KB |
testcase_21 | AC | 1,909 ms
86,456 KB |
testcase_22 | AC | 1,906 ms
86,028 KB |
testcase_23 | AC | 1,910 ms
86,196 KB |
testcase_24 | AC | 1,910 ms
85,780 KB |
testcase_25 | AC | 1,909 ms
86,536 KB |
testcase_26 | AC | 1,908 ms
85,364 KB |
testcase_27 | AC | 1,924 ms
86,240 KB |
testcase_28 | AC | 1,910 ms
85,912 KB |
testcase_29 | AC | 1,909 ms
85,800 KB |
testcase_30 | AC | 1,909 ms
85,744 KB |
testcase_31 | AC | 1,911 ms
86,844 KB |
testcase_32 | AC | 1,907 ms
86,160 KB |
testcase_33 | AC | 1,910 ms
86,288 KB |
testcase_34 | AC | 1,916 ms
86,216 KB |
testcase_35 | AC | 1,911 ms
86,340 KB |
testcase_36 | AC | 1,910 ms
86,812 KB |
testcase_37 | AC | 1,909 ms
85,636 KB |
testcase_38 | AC | 1,910 ms
87,280 KB |
testcase_39 | AC | 1,911 ms
85,712 KB |
testcase_40 | AC | 1,909 ms
86,780 KB |
testcase_41 | AC | 1,910 ms
85,788 KB |
testcase_42 | AC | 1,908 ms
86,496 KB |
testcase_43 | AC | 1,909 ms
85,864 KB |
testcase_44 | AC | 1,909 ms
85,964 KB |
testcase_45 | AC | 1,908 ms
85,736 KB |
testcase_46 | AC | 1,908 ms
86,492 KB |
testcase_47 | AC | 1,910 ms
86,064 KB |
testcase_48 | AC | 1,913 ms
85,940 KB |
testcase_49 | AC | 1,913 ms
85,752 KB |
ソースコード
""" Note """ #================================================== # 関数部 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.45: B[i]=1 elif rand<=0.90: B[i]=2 else: B[i]=3 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)