結果
問題 | No.62 リベリオン(Extra) |
ユーザー | char134217728 |
提出日時 | 2018-01-07 21:41:39 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 55 ms / 5,000 ms |
コード長 | 3,599 bytes |
コンパイル時間 | 2,114 ms |
コンパイル使用メモリ | 206,728 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-06 00:33:52 |
合計ジャッジ時間 | 2,653 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 12 ms
5,376 KB |
testcase_03 | AC | 12 ms
5,376 KB |
testcase_04 | AC | 55 ms
5,376 KB |
コンパイルメッセージ
main.cpp:117:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 117 | main(){ | ^~~~
ソースコード
#include <bits/stdc++.h> #define FOR(i,a,b) for (int i=(a);i<(b);i++) #define FORR(i,a,b) for (int i=(a);i>=(b);i--) #define pb push_back #define pcnt __builtin_popcount #define show(x) cout<<#x<<" = "<<x<<endl; #define maxs(x,y) x = max(x,y) #define mins(x,y) x = min(x,y) #define fi first #define se second #define rng(a) (a.begin()),(a.end()) #define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++) #define sz(x) (int)(x).size() #define mp make_pair using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<pii> vpii; typedef set<int> si; typedef pair<ll,ll> pll; typedef vector<ll> vl; typedef vector<vl> vvl; typedef vector<pll> vpll; typedef set<ll> sl; typedef __int128_t lll; typedef pair<lll,lll> plll; typedef vector<lll> vlll; template<typename T>string join(vector<T>&v) {stringstream s;FOR(i,0,sz(v))s<<' '<<v[i];return s.str().substr(1);} int modpow(ll a,ll n,int m){if(a==0)return a;ll p=1;for(;n>0;n/=2,a=a*a%m)if(n&1)p=p*a%m;return(int)p;} void dout(double d){printf("%.12f\n",d);} const int iinf = 1e9; const ll linf = 1e18; const int mod = 1e9+7; const double pi = acos(-1); const double eps = 1e-10; struct Ieq{ lll gcd(lll a,lll b){if(a>b)swap(a,b);for(;a>0;b%=a,swap(a,b));return b;} lll abs(lll a){return (a<0 ? -a : a);} plll _solve(lll x,lll y,lll z){ if(x==1)return plll(z,0); lll m = y/x, _y = y%x, f, s, d; plll t = _solve(_y,x,z); f = t.second - m*t.first; s = t.first; if(f<0){ d = abs(f/y); f += d*y; s -= d*x; } if(s<0){ d = abs(s/x); s += d*x; f-=d*y; } return plll(f,s); } plll solve(lll x, lll y, lll z){ if(z==0)return plll(0,0); if(z<0){ x*=-1; y*=-1; z*=-1; } ll _x=abs(x), _y=abs(y), g=gcd(_x,_y); if(g<1||z%g>0) return plll(0, 0); _x /= g; _y /= g; z /= g; if(_x > _y) swap(_x, _y); plll t = _solve(_x,_y,z); if(abs(x)>abs(y)) swap(t.first, t.second); if(x < 0)t.first *= -1; if(y < 0)t.second *= -1; return t; } }; Ieq ieq; int q; bool hit(lll w, lll h, lll d, lll x, lll y, lll vx, lll vy){ lll z = y*vx - x*vy; if(z == 0){ return (x <= vx * d &&y <= vy * d); }else{ plll t = ieq.solve(w*vy, -h*vx, z); if(t.fi == 0 && t.se == 0) return false; if(t.fi * w * vy - t.se * h * vx != z) cout << "FAIL\n"; lll g = ieq.gcd(w*vy, h*vx), _x = (h*vx)/g, _y = (w*vy)/g; if(t.fi < 0){ lll dd = -t.fi/_x + 1; t.fi += dd * _x; t.se += dd * _y; } if(t.se < 0){ lll dd = -t.se/_y + 1; t.fi += dd * _x; t.se += dd * _y; } { lll dd = t.fi/_x, dd2 = t.se/_y; if(dd2 < dd) dd = dd2; t.fi -= dd * _x; t.se -= dd * _y; } return (t.fi * w + x <= vx * d && t.se * y + y <= vy * d); } } main(){ cin.tie(0); ios::sync_with_stdio(false); cin >> q; FOR(j, 0, q){ ll w, h, d, mx, my, hx, hy, vx, vy, _mx, _my; cin >> w >> h >> d >> mx >> my >> hx >> hy >> vx >> vy; if(vx < 0){ mx = w - mx; hx = w - hx; vx *= -1; } if(vy < 0){ my = h - my; hy = h - hy; vy *= -1; } w *= 2; h *= 2; bool hi = false; FOR(i, 0, 4){ _mx = ((i&1) ? (w - mx) : mx) - hx; _my = ((i&2) ? (h - my) : my) - hy; if(_mx < 0) _mx += w; if(_my < 0) _my += h; if(hit(w, h, d, _mx, _my, vx, vy)){ cout << "Hit\n"; hi = true; break; } } if(!hi) cout << "Miss\n"; } return 0; }