結果
問題 | No.61 リベリオン |
ユーザー | LayCurse |
提出日時 | 2014-11-10 08:46:37 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 8 ms / 5,000 ms |
コード長 | 2,756 bytes |
コンパイル時間 | 1,185 ms |
コンパイル使用メモリ | 159,120 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-13 16:13:20 |
合計ジャッジ時間 | 1,617 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,816 KB |
testcase_02 | AC | 1 ms
6,816 KB |
testcase_03 | AC | 8 ms
6,820 KB |
testcase_04 | AC | 7 ms
6,820 KB |
testcase_05 | AC | 2 ms
6,820 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; #define REP(i,a,b) for(i=a;i<b;i++) #define rep(i,n) REP(i,0,n) #define mygc(c) (c)=getchar_unlocked() #define mypc(c) putchar_unlocked(c) #define ll long long void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);} void reader(int *x, int *y){reader(x);reader(y);} void reader(int *x, int *y, int *z){reader(x);reader(y);reader(z);} void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);} template<class T> T GCD(T a,T b){T r; while(a){r=b; b=a; a=r%a;} return b;} void extended_euclid(ll x,ll y,ll *c,ll *a,ll *b){ ll a0,a1,a2,b0,b1,b2,r0,r1,r2,q; r0=x; r1=y; a0=1; a1=0; b0=0; b1=1; while(r1>0){ q=r0/r1; r2=r0%r1; a2=a0-q*a1; b2=b0-q*b1; r0=r1; r1=r2; a0=a1; a1=a2; b0=b1; b1=b2; } *c=r0; *a=a0; *b=b0; } int solve(ll Vx, ll Vy, ll Sx, ll Sy, ll Dx, ll Dy){ if(Vx < 0) return solve(-Vx, Vy, -Sx, Sy, Dx, Dy); if(Vy < 0) return solve(Vx, -Vy, Sx, -Sy, Dx, Dy); ll VVx, VVy, X, Y, g, A, B, C, D, XX, YY, Bx, By; // printf("V %lld %lld , S %lld %lld, D %lld %lld\n",Vx,Vy,Sx,Sy,Dx,Dy); g = GCD(Vx, Vy); VVx = Vx / g; VVy = Vy / g; g = Sx / Dx; Sx -= g * Dx; g = Sy / Dy; Sy -= g * Dy; while(Sx < 0) Sx += Dx; while(Sx >= Dx) Sx -= Dx; while(Sy < 0) Sy += Dy; while(Sy >= Dy) Sy -= Dy; A = Dx * VVy; B = Dy * VVx; C = VVx * Sy - VVy * Sx; g = GCD(A,B); if(C%g) return 0; A /= g; B /= g; C /= g; // printf("ABC %lld %lld %lld\n",A,B,C); extended_euclid(A, B, &D, &X, &Y); Bx = C*X; By = -C*Y; // printf("XY %lld %lld\n",X,Y); // printf("XYB %lld %lld\n",Bx,By); if(A && B){ g = min(Bx / B, By / A); Bx -= g * B; By -= g * A; while(Bx-B >= 0 && By-A >= 0) Bx -= B, By -= A; while(Bx < 0 || By < 0) Bx += B, By += A; } else { Bx = By = 0; } // printf("XYB %lld %lld\n",Bx,By); XX = Sx + Bx * Dx; YY = Sy + By * Dy; // printf("XY %lld %lld\n",XX,YY); if(XX <= Vx && YY <= Vy) return 1; return 0; } int Q; int W, H, D, HX, HY, MX, MY, VX, VY; int main(){ int i, j, k; reader(&Q); while(Q--){ reader(&W,&H,&D); reader(&MX,&MY); reader(&HX,&HY); reader(&VX,&VY); k = 0; if(!k) k |= solve((ll)VX*D, (ll)VY*D, MX-HX, MY-HY, 2*W, 2*H); if(!k) k |= solve((ll)VX*D, (ll)VY*D, (2*W-MX)-HX, MY-HY, 2*W, 2*H); if(!k) k |= solve((ll)VX*D, (ll)VY*D, MX-HX, (2*H-MY)-HY, 2*W, 2*H); if(!k) k |= solve((ll)VX*D, (ll)VY*D, (2*W-MX)-HX, (2*H-MY)-HY, 2*W, 2*H); writer(k?"Hit\n":"Miss\n"); } return 0; }