結果

問題 No.62 リベリオン(Extra)
コンテスト
ユーザー ゴリポン先生
提出日時 2025-08-15 09:37:07
言語 D
(dmd 2.109.1)
結果
WA  
実行時間 -
コード長 1,707 bytes
コンパイル時間 4,877 ms
コンパイル使用メモリ 195,616 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-15 09:37:14
合計ジャッジ時間 5,978 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 2 WA * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/numeric.d(2999): Warning: cannot inline function `std.numeric.gcdImpl!ulong.gcdImpl`

ソースコード

diff # 

module main;
// https://kmjp.hatenablog.jp/entry/2014/11/11/0900 より
import std;

// https://qiita.com/drken/items/b97ff231e43bce50199a より
// 返り値: a と b の最大公約数
// ax + by = gcd(a, b) を満たす(x, y)が格納される
long extGcd(long a, long b, ref long x, ref long y)
{
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long d = extGcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
long W, H, D, MX, MY, HX, HY, VX, VY;
bool calc(long tx, long ty)
{
	long A = 2 * W * VY;
	long B = -2 * H * VX;
	long C = ty * VX - tx * VY + HX * VY - HY * VX;

	long g = gcd(A, -B);
	if (C % g != 0)
		return false;

	A /= g;
	B /= g;
	C /= g;

	long x, y;
	g = extGcd(B, A, y, x);

	long m = C * y % A;
	long tv = (ty + 2 * H * m - HY) / VY;

	tv %= 2 * H * A / VY;
	if (tv < 0)
		tv += 2 * H * A / VY;
	return tv <= D;
}

void main()
{
	// キューの処理
	foreach (_; 0 .. readln.chomp.to!int) {
		readln.chomp.formattedRead("%d %d %d %d %d %d %d %d %d", W, H, D, MX, MY, HX, HY, VX, VY);

		if (VX < 0) {
			MX = W - MX;
			HX = W - HX;
			VX = -VX;
		}
		if (VY < 0) {
			MY = H - MY;
			HY = H - HY;
			VY = -VY;
		}

		if (VX == 0) {
			if (MX == HX && ((MY > HY && MY - HY <= D * VY) || (MY < HY && 2 * H - MY - HY <= D * VY)))
				writeln("Hit");
			else
				writeln("Miss");
			continue;
		}
		if (VY == 0) {
			if (MY == HY && ((MX > HX && MX - HX <= D * VX) || (MX < HX && 2 * W - MX - HX <= D * VX)))
				writeln("Hit");
			else
				writeln("Miss");
			continue;
		}

		long g = gcd(VX, VY);
		D *= g;
		VX /= g;
		VY /= g;

		if (calc(MX, MY) || calc(2 * W - MX, MY) || calc(MX, 2 * H - MY) || calc(2 * W - MX, 2 * H - MY))
			writeln("Hit");
		else
			writeln("Miss");
	}
}
0