結果
問題 | No.62 リベリオン(Extra) |
ユーザー |
|
提出日時 | 2022-07-24 21:00:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 103 ms / 5,000 ms |
コード長 | 2,764 bytes |
コンパイル時間 | 2,149 ms |
コンパイル使用メモリ | 199,812 KB |
最終ジャッジ日時 | 2025-01-30 13:51:49 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 3 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define rep(i,n) for(ll i=0;i<n;i++)#define repl(i,l,r) for(ll i=(l);i<(r);i++)#define per(i,n) for(ll i=(n)-1;i>=0;i--)#define perl(i,r,l) for(ll i=r-1;i>=l;i--)#define fi first#define se second#define ins insert#define pqueue(x) priority_queue<x,vector<x>,greater<x>>#define all(x) (x).begin(),(x).end()#define CST(x) cout<<fixed<<setprecision(x)#define rev(x) reverse(x);using ll=long long;using vl=vector<ll>;using vvl=vector<vector<ll>>;using pl=pair<ll,ll>;using vpl=vector<pl>;using vvpl=vector<vpl>;const ll MOD=1000000007;const ll MOD9=998244353;const int inf=1e9+10;const ll INF=4e18;const ll dy[8]={1,0,-1,0,1,1,-1,-1};const ll dx[8]={0,1,0,-1,1,-1,1,-1};template <typename T> inline bool chmax(T &a, T b) {return ((a < b) ? (a = b, true) : (false));}template <typename T> inline bool chmin(T &a, T b) {return ((a > b) ? (a = b, true) : (false));}long long extGcd(long long a, long long b, long long &x, long long &y) {if (b == 0) { x = 1; y = 0; return a; }long long d = extGcd(b, a%b, y, x);y -= a/b * x;return d;}//-1が帰ってくる可能性に注意pair<long long, long long> ChineseRem(const vector<long long> &b, const vector<long long> &m) {long long r = 0, M = 1;for (int i = 0; i < (int)b.size(); ++i) {long long p, q;long long d = extGcd(M, m[i], p, q); // p is inv of M/d (mod. m[i]/d)if ((b[i] - r) % d != 0) return make_pair(0, -1);long long tmp = (b[i] - r) / d * p % (m[i]/d);r += M * tmp;M *= m[i]/d;}return make_pair((r+M+M)%M, M);}pl match(ll a,ll b,ll c){if(c==0){return make_pair(0,b/gcd(a,b));}ll x,y;if(a<0){a=-a;b=-b;c=-c;}auto g=extGcd(a,b,x,y);if(abs(c)%g){return make_pair(INF,INF);}x*=c/g;b/=g;if(b<0)b=-b;x=((x%b)+b)%b;return make_pair(x,b);}ll calc(ll w,ll h,ll d,ll mx,ll my,ll hx,ll hy,ll vx,ll vy){auto f=match(vx,w*2,mx-hx);auto g=match(vy,h*2,my-hy);if(f.first==INF||g.first==INF)return INF;//cout << f.first <<" " << f.second << endl;//cout << g.first <<" " << g.second << endl;auto ans=ChineseRem({f.first,g.first},{f.second,g.second});if(ans.second==-1)return INF;else return ans.first;}void solve(){ll w,h,d,mx,my,hx,hy,vx,vy;cin >> w >> h >> d >> mx >> my >> hx >> hy >> vx >> vy;auto g=gcd(vx,vy);d*=g;vx/=g;vy/=g;ll ans=INF;chmin(ans,calc(w,h,d,mx,my,hx,hy,vx,vy));chmin(ans,calc(w,h,d,w*2-mx,my,hx,hy,vx,vy));chmin(ans,calc(w,h,d,w*2-mx,h*2-my,hx,hy,vx,vy));chmin(ans,calc(w,h,d,mx,h*2-my,hx,hy,vx,vy));//cout << ans << endl;if(ans<=d)cout << "Hit" << endl;else cout << "Miss" << endl;}int main(){ll t;cin >> t;while(t--)solve();}