結果

問題 No.61 リベリオン
ユーザー ytftytft
提出日時 2022-11-07 01:22:03
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,435 bytes
コンパイル時間 265 ms
コンパイル使用メモリ 87,064 KB
実行使用メモリ 78,864 KB
最終ジャッジ日時 2023-09-27 17:29:00
合計ジャッジ時間 1,478 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 64 ms
71,064 KB
testcase_01 WA -
testcase_02 AC 70 ms
71,348 KB
testcase_03 RE -
testcase_04 RE -
testcase_05 AC 63 ms
71,388 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input=lambda:sys.stdin.readline().rstrip()
def gcd(a,b):
	if a*b==0:
		return a+b
	return gcd(a%b,b%a) if min(a,b,abs(a-b)) else max(a,b)
def lcm(a,b):
	return a*b//gcd(a,b)
def euclid(a,b,c):
    if a==b==0:
        return [[1,1],-1][c!=0]
    if a<0 or b<0:
        temp=euclid(abs(a),abs(b),c)
        return -1 if temp==-1 else [[-1,1][a<0]*temp[0],[-1,1][b<0]*temp[1]]
    if a==0:
        return -1 if c%b else [0,-c//b]
    if b==0:
        return -1 if c%a else [-c//a,0]
    if b>a:
        temp=euclid(a,b%a,c)
        return -1 if temp==-1 else [temp[0]-(b//a)*temp[1],temp[1]]
    else:
        temp=euclid(a%b,b,c)
        return -1 if temp==-1 else [temp[0],temp[1]-(a//b)*temp[0]]
def calc(W,M,H,V):
	ans=[0 for i in range(2)]
	g=gcd(abs(V),abs(2*W))
	right=[H-M,2*W-H-M]
	for i in range(2):
		temp=euclid(V,2*W,right[i])
		ans[i]=-1 if temp==-1 else [temp[0],2*W//gcd(2*W,V)]
	return ans
def solve():
	temp=list(map(int,input().split()))
	temp[:3]=[temp[2]]+temp[:2]
	g=gcd(abs(temp[7]),abs(temp[8]))
	temp[0]*=g
	temp[7]//=g
	temp[8]//=g
	flg=0
	r=[calc(*temp[i::2]) for i in range(1,3)]
	for i in range(4):
		ret=[r[0][i%2],r[1][i//2]]
		if -1 in ret:
			continue
		cal=euclid(ret[0][1],-ret[1][1],ret[1][0]-ret[0][0])
		if cal==-1:
			continue
		R=cal[0]*ret[0][1]+ret[0][0]
		R%=lcm(abs(ret[0][1]),abs(ret[1][1]))
		flg|=(R<=temp[0])
	print(["Miss","Hit"][flg])
N=int(input())
for i in range(N):
	solve()
0