結果
| 問題 |
No.62 リベリオン(Extra)
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:24:47 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,702 bytes |
| コンパイル時間 | 952 ms |
| コンパイル使用メモリ | 90,820 KB |
| 実行使用メモリ | 6,272 KB |
| 最終ジャッジ日時 | 2025-05-14 13:25:46 |
| 合計ジャッジ時間 | 1,474 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 2 WA * 1 |
ソースコード
#include <iostream>
#include <vector>
#include <cmath>
#include <numeric> // For std::gcd in C++17
// Extended Euclidean Algorithm: a*x + b*y = gcd(a,b)
// returns gcd(a,b), stores x and y in *x_out, *y_out
long long extended_gcd_long_long(long long a, long long b, __int128_t &x, __int128_t &y) {
if (a == 0) {
x = 0;
y = 1;
return std::abs(b); // GCD is non-negative
}
__int128_t x1, y1;
long long gcd_val_ll = extended_gcd_long_long(b % a, a, x1, y1);
x = y1 - (static_cast<__int128_t>(b) / a) * x1; // Ensure __int128_t division
y = x1;
return gcd_val_ll; // Already absolute from base case
}
// Helper to check if an integer exists in a given range
// For (low_val, high_val]
bool check_int_exists_low_exc_high_inc(long double low_val, long double high_val) {
// Smallest integer m is floor(low_val + eps_strict) + 1
// Largest integer m is floor(high_val + eps_safe_for_floor)
// Need floor(low_val + 1e-9L) + 1 <= floor(high_val + 1e-9L)
return std::floor(low_val + 1e-9L) + 1 <= std::floor(high_val + 1e-9L);
}
// For [low_val, high_val)
bool check_int_exists_low_inc_high_exc(long double low_val, long double high_val) {
// Smallest integer m is ceil(low_val - eps_safe_for_ceil)
// Largest integer m is floor(high_val - eps_strict)
// Need ceil(low_val - 1e-9L) <= floor(high_val - 1e-9L)
return std::ceil(low_val - 1e-9L) <= std::floor(high_val - 1e-9L);
}
void solve() {
long long W_ll, H_ll, D_ll_param;
long long Mx_ll, My_ll, Hx_ll, Hy_ll;
long long Vx_ll, Vy_ll;
std::cin >> W_ll >> H_ll >> D_ll_param >> Mx_ll >> My_ll >> Hx_ll >> Hy_ll >> Vx_ll >> Vy_ll;
__int128_t W = W_ll;
__int128_t H = H_ll;
__int128_t D_val = D_ll_param;
__int128_t Mx = Mx_ll;
__int128_t My = My_ll;
__int128_t Hx = Hx_ll;
__int128_t Hy = Hy_ll;
__int128_t Vx = Vx_ll;
__int128_t Vy = Vy_ll;
for (int sx_idx = 0; sx_idx < 2; ++sx_idx) {
for (int sy_idx = 0; sy_idx < 2; ++sy_idx) {
__int128_t s_x = (sx_idx == 0) ? 1 : -1;
__int128_t s_y = (sy_idx == 0) ? 1 : -1;
__int128_t current_Mx = s_x * Mx;
__int128_t current_My = s_y * My;
if (Vx == 0 && Vy == 0) {
continue;
}
if (Vx != 0 && Vy != 0) {
__int128_t A_LDE = 2 * W * Vy;
__int128_t B_LDE = -2 * H * Vx;
__int128_t C_LDE = Vx * (current_My - Hy) - Vy * (current_Mx - Hx);
__int128_t x_sol, y_sol; // For kx_part, ky_part
long long common_divisor_ll = extended_gcd_long_long( (long long)A_LDE, (long long)B_LDE, x_sol, y_sol);
__int128_t common_divisor = common_divisor_ll;
if (common_divisor == 0) { // Should ideally not happen if Vx,Vy,W,H non-zero
if (C_LDE == 0) { /* Undefined, depends on problem interpretation for 0=0. Assume this path means Vx or Vy is 0 */ }
else { continue; } // 0 = non-zero C_LDE impossible
}
if (C_LDE % common_divisor != 0) {
continue;
}
__int128_t k_x_part_num = x_sol * (C_LDE / common_divisor);
__int128_t Term_const = (current_Mx - Hx) + 2 * W * k_x_part_num;
__int128_t Term_coeff_m = (2 * W * B_LDE) / common_divisor;
// = 2*W*(-2*H*Vx)/common_divisor = -4*W*H*Vx/common_divisor
// Target:
// If Vx > 0: 0 < (Term_const + m * Term_coeff_m) <= D_val * Vx
// If Vx < 0: D_val * Vx <= (Term_const + m * Term_coeff_m) < 0
if (Term_coeff_m == 0) { // Bullet path is parallel to grid lines defined by k_x, k_y relation
bool check_satisfied = false;
if (Vx > 0) {
if (Term_const > 0 && Term_const <= D_val * Vx) check_satisfied = true;
} else { // Vx < 0
if (Term_const >= D_val * Vx && Term_const < 0) check_satisfied = true;
}
if (check_satisfied) {
// Need to verify that the corresponding y equation time is also valid
// This is implicitly handled by LDE setup. If Term_coeff_m is 0, then t is fixed for specific kx,ky.
std::cout << "Hit\n"; return;
} else {
continue;
}
}
// Let expression be E = Term_const + m * Term_coeff_m
// If Vx > 0: 0 < E <= D_val * Vx
// -(Term_const) < m * Term_coeff_m <= D_val * Vx - Term_const
// If Vx < 0: D_val * Vx <= E < 0
// D_val * Vx - Term_const <= m * Term_coeff_m < -(Term_const)
__int128_t LHS_m_mult, RHS_m_mult; // LHS_m_mult op1 m*Term_coeff_m op2 RHS_m_mult
bool lhs_strict, rhs_strict;
if (Vx > 0) {
LHS_m_mult = -Term_const; lhs_strict = true; // L < m*X
RHS_m_mult = D_val * Vx - Term_const; rhs_strict = false; // m*X <= R
} else { // Vx < 0
LHS_m_mult = D_val * Vx - Term_const; lhs_strict = false; // L <= m*X
RHS_m_mult = -Term_const; rhs_strict = true; // m*X < R
}
long double m_low_bound, m_high_bound;
if (Term_coeff_m > 0) {
m_low_bound = static_cast<long double>(LHS_m_mult) / Term_coeff_m;
m_high_bound = static_cast<long double>(RHS_m_mult) / Term_coeff_m;
if (lhs_strict && !rhs_strict) { // (low, high]
if (check_int_exists_low_exc_high_inc(m_low_bound, m_high_bound)) { std::cout << "Hit\n"; return; }
} else { // [low, high) -- Vx < 0 case
if (check_int_exists_low_inc_high_exc(m_low_bound, m_high_bound)) { std::cout << "Hit\n"; return; }
}
} else { // Term_coeff_m < 0 (must be non-zero here)
// Inequalities flip when dividing by negative Term_coeff_m
m_low_bound = static_cast<long double>(RHS_m_mult) / Term_coeff_m; // new low bound
m_high_bound = static_cast<long double>(LHS_m_mult) / Term_coeff_m; // new high bound
// original: LHS op1 m*X op2 RHS
// new: RHS/X op2_flipped m op1_flipped LHS/X
if (lhs_strict && !rhs_strict) { // original (LHS,RHS], new [low, high) for m
if (check_int_exists_low_inc_high_exc(m_low_bound, m_high_bound)) { std::cout << "Hit\n"; return; }
} else { // original [LHS,RHS), new (low, high] for m
if (check_int_exists_low_exc_high_inc(m_low_bound, m_high_bound)) { std::cout << "Hit\n"; return; }
}
}
} else if (Vx == 0 && Vy != 0) {
if ((Hx - current_Mx) % (2*W) != 0) {
continue;
}
__int128_t expr_y_base = current_My - Hy;
long double ky_low_bound, ky_high_bound;
if (Vy > 0) { // 0 < expr_y_base + 2*ky*H <= D_val*Vy
// -expr_y_base < 2*ky*H <= D_val*Vy - expr_y_base
ky_low_bound = static_cast<long double>(-expr_y_base) / (2.0L * H);
ky_high_bound = static_cast<long double>(D_val * Vy - expr_y_base) / (2.0L * H);
if (check_int_exists_low_exc_high_inc(ky_low_bound, ky_high_bound)) { std::cout << "Hit\n"; return; }
} else { // Vy < 0. D_val*Vy <= expr_y_base + 2*ky*H < 0
// (D_val*Vy - expr_y_base) <= 2*ky*H < -expr_y_base
ky_low_bound = static_cast<long double>(D_val * Vy - expr_y_base) / (2.0L * H);
ky_high_bound = static_cast<long double>(-expr_y_base) / (2.0L * H);
if (check_int_exists_low_inc_high_exc(ky_low_bound, ky_high_bound)) { std::cout << "Hit\n"; return; }
}
} else if (Vx != 0 && Vy == 0) {
if ((Hy - current_My) % (2*H) != 0) {
continue;
}
__int128_t expr_x_base = current_Mx - Hx;
long double kx_low_bound, kx_high_bound;
if (Vx > 0) { // -expr_x_base < 2*kx*W <= D_val*Vx - expr_x_base
kx_low_bound = static_cast<long double>(-expr_x_base) / (2.0L * W);
kx_high_bound = static_cast<long double>(D_val * Vx - expr_x_base) / (2.0L * W);
if (check_int_exists_low_exc_high_inc(kx_low_bound, kx_high_bound)) { std::cout << "Hit\n"; return; }
} else { // Vx < 0. (D_val*Vx - expr_x_base) <= 2*kx*W < -expr_x_base
kx_low_bound = static_cast<long double>(D_val * Vx - expr_x_base) / (2.0L * W);
kx_high_bound = static_cast<long double>(-expr_x_base) / (2.0L * W);
if (check_int_exists_low_inc_high_exc(kx_low_bound, kx_high_bound)) { std::cout << "Hit\n"; return; }
}
}
}
}
std::cout << "Miss\n";
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int Q_tc;
std::cin >> Q_tc;
while (Q_tc--) {
solve();
}
return 0;
}