#1024182 (PyPy3) No.2968 Final MIGISITA Strike

提出ソース

結果

問題	No.2968 Final MIGISITA Strike
ユーザー	ねしん
提出日時	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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	43 ms 53,504 KB
testcase_01	AC	46 ms 53,248 KB
testcase_02	AC	44 ms 53,248 KB
testcase_03	AC	44 ms 53,632 KB
testcase_04	AC	44 ms 53,376 KB
testcase_05	AC	45 ms 53,632 KB
testcase_06	AC	45 ms 53,376 KB
testcase_07	AC	44 ms 53,248 KB
testcase_08	AC	45 ms 53,504 KB
testcase_09	AC	46 ms 53,504 KB
testcase_10	AC	983 ms 117,796 KB
testcase_11	AC	1,067 ms 121,456 KB
testcase_12	AC	464 ms 92,592 KB
testcase_13	AC	656 ms 102,144 KB
testcase_14	AC	412 ms 90,720 KB
testcase_15	AC	1,443 ms 134,556 KB
testcase_16	AC	1,495 ms 133,600 KB
testcase_17	AC	1,166 ms 120,044 KB
testcase_18	AC	725 ms 101,808 KB
testcase_19	AC	993 ms 114,344 KB
testcase_20	AC	1,189 ms 126,716 KB
testcase_21	AC	440 ms 87,488 KB
testcase_22	AC	662 ms 97,412 KB
testcase_23	AC	1,589 ms 142,084 KB
testcase_24	AC	1,624 ms 142,152 KB
testcase_25	AC	1,844 ms 151,448 KB
testcase_26	AC	637 ms 98,432 KB
testcase_27	AC	1,031 ms 120,180 KB
testcase_28	AC	632 ms 94,224 KB
testcase_29	AC	822 ms 103,912 KB
testcase_30	AC	250 ms 82,944 KB
testcase_31	AC	238 ms 82,432 KB
testcase_32	AC	267 ms 83,840 KB
testcase_33	AC	238 ms 82,560 KB
testcase_34	AC	690 ms 100,388 KB
testcase_35	AC	630 ms 100,416 KB
testcase_36	AC	256 ms 79,748 KB
testcase_37	AC	555 ms 94,392 KB
testcase_38	AC	539 ms 93,728 KB
testcase_39	AC	558 ms 95,036 KB
testcase_40	AC	732 ms 102,944 KB
testcase_41	AC	468 ms 85,888 KB
testcase_42	AC	433 ms 88,600 KB
testcase_43	AC	611 ms 93,696 KB
testcase_44	AC	962 ms 111,784 KB
testcase_45	AC	365 ms 82,128 KB
testcase_46	AC	1,128 ms 119,764 KB
testcase_47	AC	707 ms 96,812 KB
testcase_48	AC	810 ms 107,224 KB
testcase_49	AC	82 ms 70,912 KB
testcase_50	AC	417 ms 83,640 KB
testcase_51	AC	659 ms 99,248 KB
testcase_52	AC	608 ms 98,152 KB
testcase_53	AC	748 ms 95,904 KB
testcase_54	AC	354 ms 83,456 KB
testcase_55	AC	1,009 ms 113,972 KB
testcase_56	AC	582 ms 95,416 KB
testcase_57	AC	1,019 ms 116,492 KB
testcase_58	AC	833 ms 108,004 KB
testcase_59	AC	524 ms 93,056 KB
testcase_60	AC	459 ms 91,224 KB
testcase_61	AC	422 ms 88,760 KB
testcase_62	AC	845 ms 108,416 KB
testcase_63	AC	847 ms 108,416 KB
testcase_64	AC	43 ms 53,632 KB
testcase_65	AC	320 ms 93,952 KB
testcase_66	AC	333 ms 95,744 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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)

yukicoder

結果

テストケース

ソースコード