結果

問題 No.62 リベリオン(Extra)
ユーザー GOTKAKO
提出日時 2025-06-29 19:48:43
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 75 ms / 5,000 ms
コード長 1,882 bytes
コンパイル時間 6,767 ms
コンパイル使用メモリ 470,772 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-06-29 19:48:53
合計ジャッジ時間 7,643 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
using bigint = boost::multiprecision::cpp_int;

bigint extgcd(bigint a, bigint b, bigint &x,bigint &y){
    //cout << a << " " << b << endl;
    if(b == 0){x = 1,y = 0; return a;}
    bigint nb = a%b;
    if(nb < 0) nb += b;
    bigint g = extgcd(b,nb,y,x);
    y -= a/b*x; return g;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int Q; cin >> Q;
    while(Q--){
        long long W,H,D,Mx,My,Hx,Hy,Vx,Vy;
        cin >> W >> H >> D >> Mx >> My >> Hx >> Hy >> Vx >> Vy;
        if(Vx < 0) Vx = -Vx,Mx = W-Mx,Hx = W-Hx;
        if(Vy < 0) Vy = -Vy,My = H-My,Hy = H-Hy;

        if(Vx == 0){
            if(Mx == Hx && ((My > Hy && (My-Hy) <= D*Vy) || (My < Hy && (2*H-My-Hy) <= D*Vy))) cout << "Hit\n";
            else cout << "Miss\n";
            continue;
        }
        if(Vy == 0){
            if(My == Hy && ((Mx > Hx && (Mx-Hx) <= D*Vx) || (Mx < Hx && (2*W-Mx-Hx) <= D*Vx))) cout << "Hit\n";
            else cout << "Miss\n";
            continue;
        }
        auto solve = [&](__int128_t Gx,__int128_t Gy) -> bool {
            bigint A = 2*W*Vy,B = -2*H*Vx,C = (Gy-Hy)*Vx-(Gx-Hx)*Vy;
            bigint x,y,g = gcd(A,-B);
            if(C%g != 0) return false;
            A /= g,B /= g,C /= g;
            extgcd(B,A,y,x);
            bigint m = C*y%A;
            if(m < 0) m += A;

            //assert((m*H*2+Gy-Hy)%Vy == 0);
            bigint t = (m*H*2+Gy-Hy)/Vy;
            
            t %= A*2*H/Vy;
            if(t < 0) t += A*2*H/Vy;
            return t<=D;
        };
        long long g = gcd(Vx,Vy);
        D *= g; Vx /= g,Vy /= g;
        if(solve(Mx,My)||solve(Mx,2*H-My)||solve(2*W-Mx,My)||solve(2*W-Mx,2*H-My)) cout << "Hit\n";
        else cout << "Miss\n";
    }
}
0