結果

問題 No.61 リベリオン
ユーザー 👑 hos.lyrichos.lyric
提出日時 2019-04-08 15:34:16
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 308 ms / 5,000 ms
コード長 4,336 bytes
コンパイル時間 1,163 ms
コンパイル使用メモリ 131,244 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-04 00:25:06
合計ジャッジ時間 2,387 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

import std.conv, std.functional, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.container, std.math, std.numeric, std.range, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }

bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }

int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }


Int gojo(Int)(in Int a, in Int b, out Int x, out Int y) {
  if (b != 0) { Int g = gojo(b, a % b, y, x); y -= (a / b) * x; return g; }
  x = 1; y = 0; return a;
}

void main() {
  try {
    for (; ; ) {
      const numCases = readInt();
      foreach (caseId; 0 .. numCases) {
        const W = BigInt(readToken());
        const H = BigInt(readToken());
        const D = BigInt(readToken());
        const MX = BigInt(readToken());
        const MY = BigInt(readToken());
        const HX = BigInt(readToken());
        const HY = BigInt(readToken());
        const VX = BigInt(readToken());
        const VY = BigInt(readToken());
        
        /*
          HX + VX t = 2 W m + r MX
          HY + VY t = 2 M n + s MY
          
          HX VY + VX VY t = 2 W VY m + r MX VY
          HY VX + VX VY t = 2 M VX n + s MY VX
          
          2 W VY m - 2 M VX n = (HX VY - HY VX) - (r MX VY - s MY VX)
        */
        bool ans;
        foreach (r; [+1, -1]) foreach (s; [+1, -1]) {
          const a = 2 * W * VY;
          const b = -2 * H * VX;
          const c = (HX * VY - HY * VX) - (r * MX * VY - s * MY * VX);
          debug {
            writefln("r = %s, s = %s; a = %s, b = %s, c = %s", r, s, a, b, c);
          }
          BigInt x, y;
          BigInt g = gojo(a, b, x, y);
          if (c % g == 0) {
            BigInt m = x * (c / g);
            BigInt n = y * (c / g);
            debug {
              writefln("  (m, n) = (%s, %s) + k (%s, %s)", m, n, -b / g, a / g);
            }
            assert(a * m + b * n == c);
            BigInt p, dp, q;
            if (VX != 0) {
              p = 2 * W * m + r * MX - HX;
              dp = 2 * W * (-b / g);
              q = VX;
            } else if (VY != 0) {
              p = 2 * H * n + s * MY - HY;
              dp = 2 * H * (a / g);
              q = VY;
            } else {
              assert(false);
            }
            if (q < 0) {
              p *= -1;
              dp *= -1;
              q *= -1;
            }
            assert(HX * q + VX * p == (2 * W * m + r * MX) * q);
            assert(HY * q + VY * p == (2 * H * n + s * MY) * q);
            assert(HX * q + VX * (p + dp) == (2 * W * (m - b / g) + r * MX) * q);
            assert(HY * q + VY * (p + dp) == (2 * H * (n + a / g) + s * MY) * q);
            dp = abs(dp);
            assert(dp > 0);
            p = (p % dp + dp) % dp;
            debug {
              writefln("  t = (%s + %s k) / %s", p, dp, q);
            }
            assert((HX * q + VX * p - r * MX * q) % (2 * W * q) == 0);
            assert((HY * q + VY * p - s * MY * q) % (2 * H * q) == 0);
            debug {
              writefln("  %s + %s (%s / %s) = 2 * %s * %s + %s * %s", HX, VX, p, q, W,
                       (HX * q + VX * p - r * MX * q) / (2 * W * q), r, MX);
              writefln("  %s + %s (%s / %s) = 2 * %s * %s + %s * %s", HY, VY, p, q, H,
                       (HY * q + VY * p - s * MY * q) / (2 * H * q), s, MY);
            }
            // p / q <= D
            if (p <= D * q) {
              ans = true;
            }
          }
        }
        writeln(ans ? "Hit" : "Miss");
      }
    }
  } catch (EOFException e) {
  }
}
0