結果
| 問題 | No.2968 Final MIGISITA Strike |
| ユーザー |
 ねしん
|
| 提出日時 | 2024-10-24 10:45:11 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
RE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 5,413 bytes |
| コンパイル時間 | 270 ms |
| コンパイル使用メモリ | 82,560 KB |
| 実行使用メモリ | 69,360 KB |
| 最終ジャッジ日時 | 2024-11-06 21:59:23 |
| 合計ジャッジ時間 | 7,394 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | RE | - |
| testcase_01 | RE | - |
| testcase_02 | RE | - |
| testcase_03 | RE | - |
| testcase_04 | RE | - |
| testcase_05 | RE | - |
| testcase_06 | RE | - |
| testcase_07 | RE | - |
| testcase_08 | RE | - |
| testcase_09 | RE | - |
| testcase_10 | RE | - |
| testcase_11 | RE | - |
| testcase_12 | RE | - |
| testcase_13 | RE | - |
| testcase_14 | RE | - |
| testcase_15 | RE | - |
| testcase_16 | RE | - |
| testcase_17 | RE | - |
| testcase_18 | RE | - |
| testcase_19 | RE | - |
| testcase_20 | RE | - |
| testcase_21 | RE | - |
| testcase_22 | RE | - |
| testcase_23 | RE | - |
| testcase_24 | RE | - |
| testcase_25 | RE | - |
| testcase_26 | RE | - |
| testcase_27 | RE | - |
| testcase_28 | RE | - |
| testcase_29 | RE | - |
| testcase_30 | RE | - |
| testcase_31 | RE | - |
| testcase_32 | RE | - |
| testcase_33 | RE | - |
| testcase_34 | RE | - |
| testcase_35 | RE | - |
| testcase_36 | RE | - |
| testcase_37 | RE | - |
| testcase_38 | RE | - |
| testcase_39 | RE | - |
| testcase_40 | RE | - |
| testcase_41 | RE | - |
| testcase_42 | RE | - |
| testcase_43 | RE | - |
| testcase_44 | RE | - |
| testcase_45 | RE | - |
| testcase_46 | RE | - |
| testcase_47 | RE | - |
| testcase_48 | RE | - |
| testcase_49 | RE | - |
| testcase_50 | RE | - |
| testcase_51 | RE | - |
| testcase_52 | RE | - |
| testcase_53 | RE | - |
| testcase_54 | RE | - |
| testcase_55 | RE | - |
| testcase_56 | RE | - |
| testcase_57 | RE | - |
| testcase_58 | RE | - |
| testcase_59 | RE | - |
| testcase_60 | RE | - |
| testcase_61 | RE | - |
| testcase_62 | RE | - |
| testcase_63 | RE | - |
| testcase_64 | RE | - |
| testcase_65 | RE | - |
| testcase_66 | RE | - |
ソースコード
#https://qiita.com/AkariLuminous/items/3e2c80baa6d5e6f3abe9からお借りしています。
import math
MOD=998244353
def inv_gcd(a, b):
a %= b
if a == 0: return b, 0
# 初期状態
s, t = b, a
m0, m1 = 0, 1
while t:
# 遷移の準備
u = s // t
# 遷移
s -= t * u
m0 -= m1 * u
# swap
s, t = t, s
m0, m1 = m1, m0
if m0 < 0: m0 += b // s
return s, m0
def crt(r, m):
assert len(r) == len(m)
n = len(r)
r0, m0 = 0, 1 # 初期値 x = 0 (mod 1)
for i in range(n):
assert m[i] >= 1
#r1, m1は遷移に使う値
r1, m1 = r[i] % m[i], m[i]
#m0がm１以上になるようにする。
if m0 < m1:
r0, r1 = r1, r0
m0, m1 = m1, m0
# m0がm1の倍数のとき gcdはm1、lcmはm0
# 解が存在すれば何も変わらないので以降の手順はスキップ
if m0 % m1 == 0:
if r0 % m1 != r1: return [0, 0]
continue
# 拡張ユークリッドの互除法によりgcd(m0, m1)と m0 * im = gcd (mod m1) を満たす imを求める
g, im = inv_gcd(m0, m1)
# 解の存在条件の確認
if (r1 - r0) % g: return [0, 0]
"""
r0, m0の遷移
コメントアウト部分はACLでの実装
C++なのでlong longを超えないようにしている
C++ はlcm(m0, m1)で割った余りが負になり得る
"""
# u1 = m1 // g
# x = (r1 - r0) // g % u1 * im % u1
# r0 += x * m0
# m0 *= u1
u1 = m0 * m1 // g
r0 += (r1 - r0) // g * m0 * im % u1
m0 = u1
#if r0 < 0: r0 += m0
return [r0, m0]
H,W,N,M,S,C,X,Y=list(map(int,input().split()))
x=[]
y=[]
a=[]
b=[]
A=list(map(int,input().split()))
B=list(map(int,input().split()))
for i in range(N):
xn,yn=list(map(int,input().split()))
x.append(xn)
y.append(yn)
for i in range(M):
xn,yn=list(map(int,input().split()))
a.append(xn)
b.append(yn)
m=[2*H,2*W]
syuuki=math.lcm(2*H,2*W)
hit=[(0,0),(syuuki,0)]
for i in range(N):
r=[-X+x[i],Y-y[i]]
z,n=crt(r,m)
if n!=0:
hit.append((z,A[i],x[i],y[i]))
r=[-X+2*H-x[i],Y-y[i]]
z,n=crt(r,m)
if n!=0:
hit.append((z,A[i],x[i],y[i]))
r=[-X+x[i],Y-2*W+y[i]]
z,n=crt(r,m)
if n!=0:
hit.append((z,A[i],x[i],y[i]))
r=[-X+2*H-x[i],Y-2*W+y[i]]
z,n=crt(r,m)
if n!=0:
hit.append((z,A[i],x[i],y[i]))
for i in range(M):
r=[-X+a[i],Y-b[i]]
z,n=crt(r,m)
if n!=0:
hit.append((z,-B[i],a[i],b[i]))
r=[-X+2*H-a[i],Y-b[i]]
z,n=crt(r,m)
if n!=0:
hit.append((z,-B[i],a[i],b[i]))
r=[-X+a[i],Y-2*W+b[i]]
z,n=crt(r,m)
if n!=0:
hit.append((z,-B[i],a[i],b[i]))
r=[-X+2*H-a[i],Y-2*W+b[i]]
z,n=crt(r,m)
if n!=0:
hit.append((z,-B[i],a[i],b[i]))
hit=sorted(hit)
rX=H-X#横の壁に当たるタイミング(mod H)
rY=Y#縦の壁に当たるタイミング(mod W)
def hitWall(s,g):#sからgまでに壁に当たる回数
ans=0
ans+=((g-rX)//H-(s-rX)//H)
ans+=((g-rY)//W-(s-rY)//W)
return ans
eventnum=len(hit)
minS=10**18
nowS=S
syuukim=-1
syuukit=0
for i in range(eventnum-1):
nowS+=hit[i][1]#キャラクターに当たった処理
if hit[i][1]>=0:
syuukim+=1
else:
syuukit+=1
hitw=hitWall(hit[i][0],hit[i+1][0])
nowS-=(hitw*C)#次のキャラクターに当たるまでの処理
minS=min(minS,nowS)#周期の中で最小値を取り出す処理
#print(nowS)
syuukiS=nowS-S#周期ごとに変動するスピード
#print(syuukiS,minS,syuukit,syuukim)
if minS<=0:#1周期目で止まる場合
#print(minS)
hm=-1
ht=0
nowS=S
for i in range(eventnum-1):
nowS+=hit[i][1]
if hit[i][1]>=0:
hm+=1
else:
ht+=1
if nowS<=0:#キャラクターに当たって止まる
print(hit[i][2],hit[i][3],hm,ht)
exit()
hitw=hitWall(hit[i][0],hit[i+1][0])
if hitw*C>=nowS:#壁に当たって止まる
ok=hit[i][0]
ng=hit[i+1][0]
while abs(ok-ng)>1:
m=(ok+ng)//2
rhit=hitWall(hit[i][0],m)
if rhit*C>=nowS:
ng=m
else:
ok=m
ansX=(X+ng)%(2*H)
ansY=(Y-ng)%(2*W)
if ansX>=H:
ansX=2*H-ansX
if ansY>=W:
ansY=2*W-ansY
print(ansX,ansY,hm,ht)
exit()
nowS-=(hitw*C)
#print(hitw,nowS)
if syuukiS>=0:#1週目で止まらず、周期ごとに加速してしまう場合
print(-1)
exit()
ok=0
ng=10**18+1
while abs(ok-ng)>1:#初めて周期内で0以下になるタイミングがある周期を探す。
m=(ok+ng)//2
if S+m*syuukiS-(S-minS)>0:
ok=m
else:
ng=m
hm=(syuukim*ng-1)%MOD
ht=(syuukit*ng)%MOD
nowS=S+ng*syuukiS
for i in range(eventnum-1):
nowS+=hit[i][1]
if hit[i][1]>=0:
hm+=1
else:
ht+=1
if nowS<=0:#キャラクターに当たって止まる
print(hit[i][2],hit[i][3],hm%MOD,ht%MOD)
exit()
hitw=hitWall(hit[i][0],hit[i+1][0])
if hitw*C>=nowS:#壁に当たって止まる
ok=hit[i][0]
ng=hit[i+1][0]
while abs(ok-ng)>1:
m=(ok+ng)//2
rhit=hitWall(hit[i][0],m)
if rhit*C>=nowS:
ng=m
else:
ok=m
ansX=(X+ng)%(2*H)
ansY=(Y-ng)%(2*W)
if ansX>=H:
ansX=2*H-ansX
if ansY>=W:
ansY=2*W-ansY
print(ansX,ansY,hm%MOD,ht%MOD)
exit()
nowS-=(hitw*C)