#1024182 (PyPy3) No.2968 Final MIGISITA Strike

• 問題: No.2968 Final MIGISITA Strike
• ユーザー: Sinonen
• 提出日時: 2024-11-03 16:05:29
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 1,844 ms / 2,525 ms
• コード長: 5,390 bytes
• コンパイル時間: 223 ms
• コンパイル使用メモリ: 82,324 KB
• 実行使用メモリ: 151,448 KB
• 最終ジャッジ日時: 2024-11-06 21:59:40
• 合計ジャッジ時間: 44,157 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

ファイルパターン	結果
other	AC * 67

ソースコード

#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=[]
B=[]

for i in range(N):
  xn,yn,an=list(map(int,input().split()))
  x.append(xn)
  y.append(yn)
  A.append(an)
  
for i in range(M):
  xn,yn,bn=list(map(int,input().split()))
  a.append(xn)
  b.append(yn)
  B.append(bn)
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)