結果

問題 No.62 リベリオン(Extra)
ユーザー t98slidert98slider
提出日時 2022-05-16 23:47:43
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,076 bytes
コンパイル時間 6,715 ms
コンパイル使用メモリ 385,920 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-14 17:06:53
合計ジャッジ時間 7,505 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using namespace boost::multiprecision;

tuple<int1024_t,int1024_t,int1024_t> ext_gcd(int1024_t p, int1024_t q){
    if(q == 0)return make_tuple(p, 1, 0);
    int1024_t g, x, y;
    tie(g, x, y) = ext_gcd(q, p%q);
    return make_tuple(g, x, y - (p/q)*x);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int1024_t W, H, D, Mx, My, Hx, Hy, Vx, Vy;
    auto calc = [&](int1024_t tx, int1024_t ty){
        int1024_t A, B, C;
        A = 2 * W * Vy;
        B = -2 * H * Vx;
        C = ty * Vx - tx * Vy + Hx * Vy - Hy * Vx;
        auto g = __gcd(A, -B);
        if(C % g != 0)return false;
        A /= g, B /= g, C /= g;
        int1024_t x, y, m, tv, v;
        tie(g, x, y) = ext_gcd(B, A);
        m = C * y % A;
        tv = (ty + 2 * H * m - Hy) / Vy;
        tv %= 2 * H * A / Vy;
        if(tv < 0)tv += 2 * H * A / Vy;
        return (tv <= D);
    };
    int t;
    cin >> t;
    while(t--){
        cin >> W >> H >> D >> Mx >> My >> Hx >> Hy >> Vx >> Vy;
        if(Vx < 0){
            Mx = W - Mx, Hx = W - Hx, Vx = -Vx;
        }
        if(Vy < 0){
            My = H - My, Hy = H - Hy, Vy = -Vy;
        }
        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 g = __gcd(Vx, Vy);
        D *= g, Vx /= g, Vy /= g;
        int1024_t Rx = 2 * W - Mx, Ry = 2 * H - My;
        if(calc(Mx, My) || calc(Mx, Ry) || calc(Rx, My) || calc(Rx, Ry)){
            cout << "Hit" << '\n';
        }else{
            cout << "Miss" << '\n';
        }
    }
}
0