結果

問題 No.61 リベリオン
ユーザー codershifthcodershifth
提出日時 2015-07-29 22:03:59
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,163 bytes
コンパイル時間 1,429 ms
コンパイル使用メモリ 145,464 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-24 21:59:52
合計ジャッジ時間 1,990 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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;

                // 格子点を移動させるため 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;
                    if (x < 0)   { Vx *= -1; x *= -1; }
                    if (x > W-1) { Vx *= -1; x = 2*W-x; }
                    if (y < 0)   { Vy *= -1; y *= -1; }
                    if (y > H-1) { Vy *= -1; y = 2*H-y; }

                    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