結果

問題 No.62 リベリオン(Extra)
コンテスト
ユーザー Unbakedbread
提出日時 2026-08-14 21:13:48
言語 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  
実行時間 38 ms / 5,000 ms
+ 561µs
コード長 1,579 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,498 ms
コンパイル使用メモリ 335,716 KB
実行使用メモリ 9,304 KB
最終ジャッジ日時 2026-08-14 21:13:52
合計ジャッジ時間 3,627 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

using ll = __int128_t;

ll gcd(ll a, ll b) {return (a % b ? gcd(b, a % b) : b);}

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() {
	int64_t aW, aH, aD, aMx, aMy, aHx, aHy, aVx, aVy;
	cin >> aW >> aH >> aD >> aMx >> aMy >> aHx >> aHy >> aVx >> aVy;
	ll W = aW, H = aH, D = aD, Mx = aMx, My = aMy, Hx = aHx, Hy = aHy, Vx = aVx, Vy = aVy;
	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