結果

問題 No.62 リベリオン(Extra)
ユーザー fumofumofunifumofumofuni
提出日時 2022-07-24 20:12:25
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,823 bytes
コンパイル時間 2,099 ms
コンパイル使用メモリ 204,816 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-20 20:24:35
合計ジャッジ時間 2,922 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ（β）

テストケース

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

ソースコード

diff # 

#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,1);
  }
  ll x,y;
  auto g=extGcd(a,b,x,y);
  //cout << a <<" " << b <<" " << c <<" " << x <<" " << y <<" " << g << endl;
  if(abs(c)%g){
    return make_pair(INF,INF);
  }
  x*=c/g;b*=c/g;if(b<0)b=-b;
  //cout << b << endl;
  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();
}
0