結果

問題 No.61 リベリオン
コンテスト
ユーザー codershifth
提出日時 2015-07-30 00:48:03
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 60 ms / 5,000 ms
コード長 2,504 bytes
コンパイル時間 1,239 ms
コンパイル使用メモリ 160,252 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-13 16:14:44
合計ジャッジ時間 1,704 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

using namespace std;

template<typename T>
T gcd(T a, T b) {
    if ( a < b )
        std::swap(a,b);
    if ( b == 0 )
        return a;
    return gcd(b, a%b);
}

class Rebellion {
public:
    void solve(void) {
            int Q;
            cin>>Q;

            // H,W の制約が小さいので 1 クエリにたいして O(16^2*4) <= 1024 程度
            // 同じ (x,y) 座標で方向が同じ場合ループになるので D は最大 1050 程度まで調べれば良い
            // シミュレーションで十分間に合う
            REP(q,Q)
            {
                int W,H,Mx,My,Hx,Hy;
                ll  D,Vx,Vy;
                cin>>W>>H>>D>>Mx>>My>>Hx>>Hy>>Vx>>Vy;

                // 1 秒ごとの移動で格子点上に移動させるため Vx,Vy は互いに素になるようにしておく
                ll k = gcd(abs(Vx),abs(Vy));
                Vx /= k;
                Vy /= k;
                D = min(1050LL, D*k);

                int x,y;
                x = Hx;
                y = Hy;
                bool hit = false;
                for (int d = 1; d <= D; ++d)
                {
                    // 1 秒経過ごとに移動させる
                    x += Vx;
                    y += Vy;

                    //  W = 3, H = 10, Vx = 15, Vy = 1
                    //  みたいなケースでは反転が複数回おこなわれるので対応
                    while (true)
                    {
                        if (x < 0) { Vx *= -1; x = -x;    continue; }
                        if (x > W) { Vx *= -1; x = 2*W-x; continue; }
                        if (y < 0) { Vy *= -1; y = -y;    continue; }
                        if (y > H) { Vy *= -1; y = 2*H-y; continue; }
                        break;
                    }

                    if (x == Mx && y == My)
                    {
                        hit = true;
                        break;
                    }
                }
                if (hit)
                    cout<<"Hit"<<endl;
                else
                    cout<<"Miss"<<endl;
            }
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new Rebellion();
        obj->solve();
        delete obj;
        return 0;
}
#endif
0