結果

問題 No.62 リベリオン(Extra)
ユーザー PachicobuePachicobue
提出日時 2017-07-15 18:27:58
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 8,620 bytes
コンパイル時間 1,793 ms
コンパイル使用メモリ 171,008 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-08 02:32:39
合計ジャッジ時間 2,494 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define show(x) cout << #x << " = " << x << endl

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
    os << "sz=" << v.size() << "\n[";
    for (const auto& p : v) {
        os << p << ",";
    }
    os << "]\n";
    return os;
}

template <typename S, typename T>
ostream& operator<<(ostream& os, const pair<S, T>& p)
{
    os << "(" << p.first << "," << p.second
       << ")";
    return os;
}


constexpr ll MOD = 1e9 + 7;

template <typename T>
constexpr T INF = numeric_limits<T>::max() / 100;

inline pair<ll, ll> extgcd(const ll x, const ll y)
{
    ll r0 = x;
    ll r1 = y;
    ll a0 = 1;
    ll a1 = 0;
    ll b0 = 0;
    ll b1 = 1;
    while (r1 > 0) {
        const ll q1 = r0 / r1;
        const ll r2 = r0 % r1;
        const ll a2 = a0 - q1 * a1;
        const ll b2 = b0 - q1 * b1;
        r0 = r1;
        r1 = r2;
        a0 = a1;
        a1 = a2;
        b0 = b1;
        b1 = b2;
    }
    return make_pair(a0 / r0, b0 / r0);
}

template <typename T>
T gcd(const T a, const T b)
{
    return b ? gcd(b, a % b) : a;
}

template <typename T>
T lcm(const T a, const T b)
{
    return (a / gcd(a, b)) * b;
}


int main()
{
    ll Q;
    cin >> Q;
    for (ll query = 0; query < Q; query++) {
        ll w, h, d, mx, my, hx, hy, vx, vy;
        cin >> w >> h >> d >> mx >> my >> hx >> hy >> vx >> vy;
        if (vx != 0 and vy != 0) {

            const ll g = gcd(vx, vy);
            d *= g;
            vx /= g;
            vy /= g;
            const ll gx = gcd(2 * w, vx);
            const ll gy = gcd(2 * h, vy);
            const ll x[2] = {hx - mx, hx + mx - 2 * w};
            const ll y[2] = {hy - my, hy + my - 2 * h};
            const ll W = 2 * w / gx;
            const ll H = 2 * h / gy;
            const ll VX = vx / gx;
            const ll VY = vy / gy;
            bool ok = false;
            for (int i = 0; i < 4; i++) {
                ll X = x[i % 2];
                ll Y = y[i / 2];
                if (X % gx != 0) {
                    continue;
                }
                X /= gx;
                if (Y % gy != 0) {
                    continue;
                }
                Y /= gy;

                // W*k-VX*t = X
                // H*l-VY*t = Y
                const pair<ll, ll> px = extgcd(W, VX);
                const pair<ll, ll> py = extgcd(H, VY);
                const ll k0 = px.first * X;
                const ll t0 = -px.second * X;
                const ll l0 = py.first * Y;
                const ll t1 = -py.second * Y;
                // show(W * k0 - VX * t0 - X);
                // show(H * l0 - VY * t1 - Y);

                // W_*i_-j_*H_ = delta_t
                const ll g_ = gcd(W, H);
                ll delta_t = t1 - t0;
                if (delta_t % g_ != 0) {
                    continue;
                }
                const ll W_ = W / g_;
                const ll H_ = H / g_;
                delta_t /= g_;
                const pair<ll, ll> pt = extgcd(W_, H_);
                const ll i_ = pt.first * delta_t;
                const ll j_ = -pt.second * delta_t;
                // show(W_ * i_ - j_ * H_ - delta_t);

                ll k = k0 + i_ * VX;
                ll l = l0 + (i_ * W_ - delta_t) / H_ * VY;
                ll t = t0 + i_ * W;
                // show(d);
                // show(k);
                // show(l);
                // show(t);
                const ll dk = H_ * VX;
                const ll dl = W_ * VY;
                const ll dt = H_ * W;
                // show(dk);
                // show(dl);
                // show(dt);

                ll minimum = -INF<ll>;
                ll maximum = INF<ll>;
                if (dk > 0) {
                    ll kmin = (-k) / dk;
                    if (dk * kmin < -k) {
                        kmin++;
                    }
                    minimum = max(minimum, kmin);
                } else if (dk < 0) {
                    ll kmax = (-k) / dk;
                    if (dk * kmax > -k) {
                        kmax--;
                    }
                    maximum = min(maximum, kmax);
                }

                if (dl > 0) {
                    ll lmin = (-l) / dl;
                    if (dl * lmin < -l) {
                        lmin++;
                    }
                    minimum = max(minimum, lmin);
                } else if (dl < 0) {
                    ll lmax = (-l) / dl;
                    if (dl * lmax > -l) {
                        lmax--;
                    }
                    maximum = min(maximum, lmax);
                }

                if (dt > 0) {
                    ll tmin = (-t) / dt;
                    if (tmin * dt < -t) {
                        tmin++;
                    }
                    ll tmax = (d - t) / dt;
                    if (tmax * dt > (d - t)) {
                        tmax--;
                    }
                    minimum = max(minimum, tmin);
                    maximum = min(maximum, tmax);
                } else if (dt < 0) {
                    ll tmin = (d - t) / dt;
                    if (tmin * dt < d - t) {
                        tmin++;
                    }
                    ll tmax = (-t) / dt;
                    if (tmax * dt > (-t)) {
                        tmax--;
                    }
                    minimum = max(minimum, tmin);
                    maximum = min(maximum, tmax);
                }
                // show(maximum);
                // show(minimum);
                if (maximum >= minimum) {
                    // show(k + dk * minimum);
                    // show(l + dl * minimum);
                    // show(t + dt * minimum);
                    ok = true;
                    break;
                }
            }
            if (ok) {
                cout << "Hit" << endl;
            } else {
                cout << "Miss" << endl;
            }
        } else if (vx == 0) {

            if (hx != mx) {
                cout << "Miss" << endl;
            } else {
                if (vy > 0) {
                    if (my - hy > 0) {
                        if (my - hy <= d * vy) {
                            cout << "Hit" << endl;
                        } else {
                            cout << "Miss" << endl;
                        }
                    } else {
                        if (2 * h - my - hy <= d * vy) {
                            cout << "Hit" << endl;
                        } else {
                            cout << "Miss" << endl;
                        }
                    }
                } else {
                    vy *= -1;
                    if (my - hy > 0) {
                        if (2 * h - hy - my <= d * vy) {
                            cout << "Hit" << endl;
                        } else {
                            cout << "Miss" << endl;
                        }
                    } else {
                        if (hy + my <= d * vy) {
                            cout << "Hit" << endl;
                        } else {
                            cout << "Miss" << endl;
                        }
                    }
                }
            }
        } else {
            if (hy != my) {
                cout << "Miss" << endl;
            } else {
                if (vx > 0) {
                    if (mx - hx > 0) {
                        if (mx - hx <= d * vx) {
                            cout << "Hit" << endl;
                        } else {
                            cout << "Miss" << endl;
                        }
                    } else {
                        if (2 * w - mx - hx <= d * vx) {
                            cout << "Hit" << endl;
                        } else {
                            cout << "Miss" << endl;
                        }
                    }
                } else {
                    vx *= -1;
                    if (mx - hx > 0) {
                        if (2 * w - hx - mx <= d * vx) {
                            cout << "Hit" << endl;
                        } else {
                            cout << "Miss" << endl;
                        }
                    } else {
                        if (hx + mx <= d * vx) {
                            cout << "Hit" << endl;
                        } else {
                            cout << "Miss" << endl;
                        }
                    }
                }
            }
        }
    }

    return 0;
}
0