結果
| 問題 | No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance |
| ユーザー |
👑  Kazun
|
| 提出日時 | 2022-07-31 15:47:53 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,896 ms / 2,000 ms |
| コード長 | 4,427 bytes |
| コンパイル時間 | 251 ms |
| 実行使用メモリ | 91,964 KB |
| スコア | 137,361,754,978,717 |
| 最終ジャッジ日時 | 2022-10-14 21:11:35 |
| 合計ジャッジ時間 | 104,283 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge12 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1,892 ms
88,188 KB |
| testcase_01 | AC | 1,885 ms
90,364 KB |
| testcase_02 | AC | 1,885 ms
89,180 KB |
| testcase_03 | AC | 1,884 ms
88,900 KB |
| testcase_04 | AC | 1,884 ms
89,388 KB |
| testcase_05 | AC | 1,880 ms
90,232 KB |
| testcase_06 | AC | 1,888 ms
90,764 KB |
| testcase_07 | AC | 1,883 ms
89,372 KB |
| testcase_08 | AC | 1,886 ms
91,592 KB |
| testcase_09 | AC | 1,886 ms
89,576 KB |
| testcase_10 | AC | 1,884 ms
91,108 KB |
| testcase_11 | AC | 1,894 ms
89,308 KB |
| testcase_12 | AC | 1,896 ms
88,828 KB |
| testcase_13 | AC | 1,888 ms
89,368 KB |
| testcase_14 | AC | 1,893 ms
90,300 KB |
| testcase_15 | AC | 1,885 ms
90,600 KB |
| testcase_16 | AC | 1,896 ms
89,216 KB |
| testcase_17 | AC | 1,883 ms
89,196 KB |
| testcase_18 | AC | 1,882 ms
91,548 KB |
| testcase_19 | AC | 1,886 ms
91,080 KB |
| testcase_20 | AC | 1,889 ms
89,740 KB |
| testcase_21 | AC | 1,892 ms
91,312 KB |
| testcase_22 | AC | 1,884 ms
90,512 KB |
| testcase_23 | AC | 1,889 ms
89,232 KB |
| testcase_24 | AC | 1,883 ms
91,128 KB |
| testcase_25 | AC | 1,884 ms
89,372 KB |
| testcase_26 | AC | 1,891 ms
88,660 KB |
| testcase_27 | AC | 1,886 ms
90,276 KB |
| testcase_28 | AC | 1,888 ms
91,012 KB |
| testcase_29 | AC | 1,889 ms
88,624 KB |
| testcase_30 | AC | 1,887 ms
89,032 KB |
| testcase_31 | AC | 1,890 ms
90,432 KB |
| testcase_32 | AC | 1,884 ms
90,544 KB |
| testcase_33 | AC | 1,886 ms
89,068 KB |
| testcase_34 | AC | 1,883 ms
88,568 KB |
| testcase_35 | AC | 1,887 ms
90,180 KB |
| testcase_36 | AC | 1,883 ms
91,344 KB |
| testcase_37 | AC | 1,886 ms
88,704 KB |
| testcase_38 | AC | 1,885 ms
89,916 KB |
| testcase_39 | AC | 1,882 ms
90,248 KB |
| testcase_40 | AC | 1,884 ms
90,420 KB |
| testcase_41 | AC | 1,885 ms
88,764 KB |
| testcase_42 | AC | 1,882 ms
90,244 KB |
| testcase_43 | AC | 1,883 ms
91,964 KB |
| testcase_44 | AC | 1,881 ms
91,688 KB |
| testcase_45 | AC | 1,883 ms
89,196 KB |
| testcase_46 | AC | 1,885 ms
90,148 KB |
| testcase_47 | AC | 1,884 ms
91,964 KB |
| testcase_48 | AC | 1,882 ms
89,816 KB |
| testcase_49 | AC | 1,883 ms
89,308 KB |
ソースコード
"""
作戦 0: 全テストケース固定の解答
作戦 1: (N-1) 個同じ離散振り子
作戦 2: 時間いっぱいランダム
作戦 3: 山登り
"""
#==================================================
# 関数部
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(X):
X=[position(i,T) for i in range(N)]
R_sum=0
for i in range(N):
for k in range(i+1,N):
R_sum+=abs(X[i]-X[k])/(B[i]+B[k])
coef=pow(10,7)*(2/(N*(N-1)))
return round(coef*R_sum)
def score_cooperation(T: int):
X=[position(i,T) for i in range(N)]
H=max(X)-min(X)
alpha=sqrt(H/20+1)
return round(pow(10,7)/alpha)
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()))
#==================================================
FIRST_PHASE=1.400
SECOND_PHASE=0.400
B=[0]*N; M=[0]*N; E=[0]*N
X=[[0]*N for _ in range(K)]
Y=[[0]*N for _ in range(K)]
#==================================================
# 第 1 部
BEGIN_TIME=time()
best_score=-1
while time()-BEGIN_TIME<FIRST_PHASE:
for i in range(N):
B[i]=randint(100,1000); M[i]=randint(100,1000)
if B[i]<M[i]:
B[i],M[i]=M[i],B[i]
E[i]=randint(0,B[i]-M[i])
for j in range(K):
for i in range(N):
X[j][i]=position(B[i],M[i],E[i],T[j])
Y[j][i]=position(B[i],M[i],E[i],U[j])
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)
if best_score<C1*C2:
best_score=C1*C2
BB=B.copy()
MM=M.copy()
EE=E.copy()
#==================================================
# 第 2 部
B=BB; M=MM; E=EE
BEGIN_TIME=time()
chance=0; change=0
while time()-BEGIN_TIME<SECOND_PHASE:
i=randint(0,N-1)
b=randint(100,1000); m=randint(100,1000)
if b<m:
b,m=m,b
e=randint(0,b-m)
B[i],b=b,B[i]; M[i],m=m,M[i]; E[i],e=e,E[i]
for j in range(K):
X[j][i]=position(B[i],M[i],E[i],T[j])
Y[j][i]=position(B[i],M[i],E[i],U[j])
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)
chance+=1
if best_score<C1*C2:
change+=1
best_score=C1*C2
else:
B[i],b=b,B[i]; M[i],m=m,M[i]; E[i],e=e,E[i]
#==================================================
for i in range(N):
print(B[i],M[i],E[i])
debug(change,"/",chance)
debug(best_score)