結果

問題 No.61 リベリオン
コンテスト
ユーザー Unbakedbread
提出日時 2026-08-14 21:06:41
言語 C++23
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 20 ms / 5,000 ms
+ 425µs
コード長 1,409 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,867 ms
コンパイル使用メモリ 338,204 KB
実行使用メモリ 7,340 KB
最終ジャッジ日時 2026-08-14 21:06:44
合計ジャッジ時間 3,096 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void ext_gcd(ll A, ll B, ll &x, ll &y) {
	if(B == 0) x = 1, y = 0;
	else {ext_gcd(B, A % B, y, x); y -= A / B * x;}
}

int solve() {
	ll W, H, D, Mx, My, Hx, Hy, Vx, Vy;
	cin >> W >> H >> D >> Mx >> My >> Hx >> Hy >> Vx >> Vy;
	H *= 2, W *= 2;
	
	if(Vx < 0) Vx = -Vx, Mx = W - Mx, Hx = W - Hx;
	if(Vy < 0) Vy = -Vy, My = H - My, Hy = H - Hy;
	
	if(Vy == 0) swap(W, H), swap(Mx, My), swap(Hx, Hy), swap(Vx, Vy);
	if(Vx == 0) {
		const ll dist = (My < Hy ? H * 2 - Hy - My : My - Hy);
		cout << (Mx == Hx and dist <= D * Vy ? "Hit" : "Miss") << "\n";
		return 0;
	}
	
	ll X = Vy * W, Y = Vx * H;
	ll G = gcd(X, Y);
	X /= G, Y /= G;
	ll sX = 0, sY = 0;
	ext_gcd(X, Y, sX, sY);
	while(sX < 0) sX += Y, sY -= X;
	sY *= -1;
	
	const auto calc = [&](ll mx, ll my) ->ll {
		mx = (mx - Hx + W) % W, my = (my - Hy + H) % H;
		ll t = Vx * my - Vy * mx;
		if(t % G) return 1e18;
		t /= G;
		if(t == 0) return (mx + Vx - 1) / Vx;
		ll kx = sX * t, ky = sY * t;
		const ll cnt = min(kx / Y, ky / X);
		kx -= cnt * Y, ky -= cnt * X;
		while(kx < 0 or ky < 0) kx += Y, ky += X;
		return (kx * W + mx + Vx - 1) / Vx;
	};
	
	const ll ans = min({calc(Mx, My), calc(W - Mx, My), calc(Mx, H - My), calc(W - Mx, H - My)});
	cout << (ans <= D ? "Hit" : "Miss") << "\n";
	return 0;
}

int main() {
	int Q;
	cin >> Q;
	while(Q--) if(solve()) return 1;
	return 0;
}
0