結果
問題 | No.62 リベリオン(Extra) |
ユーザー | anta |
提出日時 | 2015-09-26 16:22:00 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 40 ms / 5,000 ms |
コード長 | 2,856 bytes |
コンパイル時間 | 682 ms |
コンパイル使用メモリ | 82,456 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-19 10:39:12 |
合計ジャッジ時間 | 1,458 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 16 ms
5,376 KB |
testcase_03 | AC | 16 ms
5,376 KB |
testcase_04 | AC | 40 ms
5,376 KB |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:71:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 71 | scanf("%d", &Q); | ~~~~~^~~~~~~~~~ main.cpp:74:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 74 | scanf("%d%d%d", &W, &H, &D); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~ main.cpp:76:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 76 | scanf("%d%d%d%d", &Mx, &My, &Hx, &Hy); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ main.cpp:78:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 78 | scanf("%d%d", &Vx, &Vy); | ~~~~~^~~~~~~~~~~~~~~~~~
ソースコード
#include <string> #include <vector> #include <algorithm> #include <numeric> #include <set> #include <map> #include <queue> #include <iostream> #include <sstream> #include <cstdio> #include <cmath> #include <ctime> #include <cstring> #include <cctype> #include <cassert> #include <limits> #include <functional> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i)) #if defined(_MSC_VER) || __cplusplus > 199711L #define aut(r,v) auto r = (v) #else #define aut(r,v) __typeof(v) r = (v) #endif #define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it) #define all(o) (o).begin(), (o).end() #define pb(x) push_back(x) #define mp(x,y) make_pair((x),(y)) #define mset(m,v) memset(m,v,sizeof(m)) #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3fLL using namespace std; typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll; template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; } template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; } int exgcd(int a, int b, int &g) { int u = 1, v = 0; while(b) { int t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } g = a; return u; } long long crt(long long a1, long long n1, int a2, int n2, long long &resn) { int t, g; t = exgcd(n1 % n2, n2, g); if((a1 - a2) % g != 0) return -1; int n2_g = n2 / g; int d = (a2 - a1) / g % n2_g; int h = (long long)d * t % n2_g; if(h < 0) h += n2_g; long long n = n1 * n2_g; long long a = a1 + n1 * h; resn = n; return a; } inline int red(int x, int y) { int z = x % y; if(z < 0) z += y; return z; } int main() { int Q; scanf("%d", &Q); rep(ii, Q) { int W, H, D; scanf("%d%d%d", &W, &H, &D); int Mx, My, Hx, Hy; scanf("%d%d%d%d", &Mx, &My, &Hx, &Hy); int Vx, Vy; scanf("%d%d", &Vx, &Vy); int speed; { exgcd(abs(Vx), abs(Vy), speed); Vx /= speed, Vy /= speed; } ll minTime = INFL; rep(mx, 2) rep(my, 2) { int w = W * 2, h = H * 2; int x = mx == 0 ? Mx : 2 * W - Mx; int y = my == 0 ? My : 2 * H - My; x = red(x - Hx, w); y = red(y - Hy, h); int vx = red(Vx, w); int vy = red(Vy, h); int a, b; { int g; a = exgcd(vx, w, g); if(x % g != 0) continue; vx /= g, x /= g, w /= g; a = red(a, w); assert((ll)a * vx % w == 1 % w); a = (ll)a * x % w; } { int g; b = exgcd(vy, h, g); if(y % g != 0) continue; vy /= g, y /= g, h /= g; b = red(b, h); assert((ll)b * vy % h == 1 % h); b = (ll)b * y % h; } //t = a (mod w); t = b (mod h) ll dummy; ll t = crt(a, w, b, h, dummy); if(t != -1) amin(minTime, t); } bool ans = minTime <= (ll)D * speed; puts(ans ? "Hit" : "Miss"); } return 0; }