結果

問題 No.62 リベリオン(Extra)
コンテスト
ユーザー ゴリポン先生
提出日時 2025-08-15 09:59:56
言語 D
(dmd 2.109.1)
結果
WA  
実行時間 -
コード長 1,879 bytes
コンパイル時間 3,980 ms
コンパイル使用メモリ 189,708 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-15 10:00:04
合計ジャッジ時間 7,192 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 2 WA * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/numeric.d(3130): Warning: cannot inline function `std.numeric.gcdImpl!(BigInt).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)が格納される
BigInt extGcd(BigInt a, BigInt b, ref BigInt x, ref BigInt y)
{
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	BigInt d = extGcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
BigInt W, H, D, MX, MY, HX, HY, VX, VY;
bool calc(BigInt tx, BigInt ty)
{
	BigInt A = 2 * W * VY;
	BigInt B = -2 * H * VX;
	BigInt C = ty * VX - tx * VY + HX * VY - HY * VX;

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

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

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

	BigInt m = C * y % A;
	BigInt 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) {
		auto str = readln.split;
		W = BigInt(str[0]);
		H = BigInt(str[1]);
		D = BigInt(str[2]);
		MX = BigInt(str[3]);
		MY = BigInt(str[4]);
		HX = BigInt(str[5]);
		HY = BigInt(str[6]);
		VX = BigInt(str[7]);
		VY = BigInt(str[8]);

		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;
		}

		BigInt 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