#432340 (D) No.187 中華風 (Hard)

• 問題: No.187 中華風 (Hard)
• ユーザー: te-sh
• 提出日時: 2020-02-21 19:52:06
• 言語: D (dmd 2.109.1)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 9,697 bytes
• コンパイル時間: 305 ms
• コンパイル使用メモリ: 105,492 KB
• 最終ジャッジ日時: 2024-06-22 05:22:46
• 合計ジャッジ時間: 651 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

コンパイルメッセージ

Main.d(359): Deprecation: function `Main.IO!(makeGlobal, makeGlobal).IO.put!("{exit: true}", int).put.putMain!(c, int).putMain` function requires a dual-context, which is deprecated
Main.d-mixin-329(329):        instantiated from here: `putMain!(c, int)`
Main.d(14):        instantiated from here: `put!("{exit: true}", int)`
Main.d(359): Deprecation: function `Main.IO!(makeGlobal, makeGlobal).IO.put!("{}", GmpInt).put.putMain!(c, GmpInt).putMain` function requires a dual-context, which is deprecated
Main.d-mixin-329(329):        instantiated from here: `putMain!(c, GmpInt)`
Main.d(333):        instantiated from here: `put!("{}", GmpInt)`
Main.d(17):        instantiated from here: `putB!("{}", GmpInt, GmpInt)`
Main.d(121): Error: returning `this` escapes a reference to parameter `this`
Main.d(118):        perhaps annotate the function with `return`

ソースコード

// URL: https://yukicoder.me/problems/no/187

import std.algorithm, std.array, std.bitmanip, std.container, std.conv, std.format,
       std.functional, std.math, std.range, std.traits, std.typecons, std.stdio, std.string;

version(unittest) {} else
void main()
{
  int N; io.getV(N);
  int[] X, Y; io.getC(N, X, Y);

  auto x = GmpInt(X[0]), y = GmpInt(Y[0]);
  foreach (i; 1..N)
    if (!calc(x, y, GmpInt(X[i]), GmpInt(Y[i]))) io.put!"{exit: true}"(-1);

  auto mod = 10^^9+7;
  io.putB(x == 0, y%mod, x%mod);
}

auto calc(T)(ref T X1, ref T Y1, T X2, T Y2)
{
  auto r = extGcd(Y1, Y2);
  if ((X2-X1)%r.gcd != 0) return false;

  auto y1 = Y1/r.gcd, y2 = Y2/r.gcd;
  Y1 = y1*y2*r.gcd;
  X1 = pmod(r.x*y1*(X2-X1)+X1, Y1);
  return true;
}

pure nothrow @nogc @safe
{
  auto lowerBoundBy(alias conv = "a", alias comp = "a<b", R, T)(const R a, const T v)
  {
    return a.sortedTuple!(conv, comp).lowerBound(tuple(a.front, v)).map!"a[0]";
  }

  auto upperBoundBy(alias conv = "a", alias comp = "a<b", R, T)(const R a, const T v)
  {
    return a.sortedTuple!(conv, comp).upperBound(tuple(a.front, v)).map!"a[0]";
  }

  auto sortedTuple(alias conv = "a", alias comp = "a<b", R)(const R a)
  {
    alias convFun = unaryFun!conv, compFun = binaryFun!comp;
    return a.map!(e => tuple(e, convFun(e))).assumeSorted!((a, b) => compFun(a[1], b[1]));
  }
}

pure nothrow @nogc @safe
{
  T cdiv(T)(const T a, const T b)
  {
    return (a+b-1)/b;
  }
  T pmod(T)(const T a, const T b)
  {
    return a >= 0 ? a%b : a%b+b;
  }

  ExtGcdResult!T extGcd(T)(const T a, const T b)
  {
    if (a == 0) {
      return ExtGcdResult!T(T(b), T(0), T(1));
    } else {
      auto r = extGcd(b%a, a);
      return ExtGcdResult!T(r.gcd, r.y-(b/a)*r.x, r.x);
    }
  }

  private struct ExtGcdResult(T)
  {
    T gcd, x, y;
  }
}

struct GmpInt
{
  pure nothrow @nogc @safe
  {
    this(long v)
    {
      __gmpz_init_set_si(&z, v);
    }
    this(ref return scope const GmpInt v)
    {
      __gmpz_init_set(&z, &v.z);
    }
    ~this()
    {
      __gmpz_clear(&z);
    }

    long toLong() const
    {
      return __gmpz_get_si(&z);
    }

    bool opEquals(const GmpInt v) const
    {
      return __gmpz_cmp(&z, &v.z) == 0;
    }
    bool opEquals(T)(T v) const
      if (isIntegral!T)
    {
      return __gmpz_cmp_si(&z, v) == 0;
    }
    int opCmp(const GmpInt v) const
    {
      return __gmpz_cmp(&z, &v.z);
    }
    int opCmp(T)(T v) const
      if (isIntegral!T)
    {
      return __gmpz_cmp_si(&z, v);
    }

    ref GmpInt opAssign(const GmpInt v)
    {
      __gmpz_init_set(&z, &v.z);
      return this;
    }
    ref GmpInt opAssign(T)(T v)
      if (isIntegral!T)
    {
      __gmpz_init_set_si(&z, v);
      return this;
    }

    GmpInt opBinary(string op)(const GmpInt v) const
      if (op == "+" || op == "-" || op == "*" || op == "/" || op == "%")
    {
      auto r = GmpInt(0);
      static      if (op == "+") __gmpz_add(&r.z, &z, &v.z);
      else static if (op == "-") __gmpz_sub(&r.z, &z, &v.z);
      else static if (op == "*") __gmpz_mul(&r.z, &z, &v.z);
      else static if (op == "/") __gmpz_tdiv_q(&r.z, &z, &v.z);
      else static if (op == "%") __gmpz_tdiv_r(&r.z, &z, &v.z);
      return r;
    }
    ref GmpInt opOpAssign(string op)(const GmpInt v)
      if (op == "+" || op == "-" || op == "*" || op == "/" || op == "%")
    {
      static      if (op == "+") __gmpz_add(&z, &z, &v.z);
      else static if (op == "-") __gmpz_sub(&z, &z, &v.z);
      else static if (op == "*") __gmpz_mul(&z, &z, &v.z);
      else static if (op == "/") __gmpz_tdiv_q(&z, &z, &v.z);
      else static if (op == "%") __gmpz_tdiv_r(&z, &z, &v.z);
      return this;
    }

    GmpInt opBinary(string op, U)(U v) const
      if ((op == "+" || op == "-" || op == "*" || op == "/" || op == "%" || op == "^^")
          && isIntegral!U)
    {
      auto r = GmpInt(0);
      static      if (op == "+") __gmpz_add_ui(&r.z, &z, v);
      else static if (op == "-") __gmpz_sub_ui(&r.z, &z, v);
      else static if (op == "*") __gmpz_mul_ui(&r.z, &z, v);
      else static if (op == "/") __gmpz_tdiv_q_ui(&r.z, &z, v);
      else static if (op == "%") __gmpz_tdiv_r_ui(&r.z, &z, v);
      else static if (op == "^^") __gmpz_pow_ui(&r.z, &z, v);
      return r;
    }
    ref GmpInt opOpAssign(string op, U)(U v)
      if ((op == "+" || op == "-" || op == "*" || op == "/" || op == "%" || op == "^^")
          && isIntegral!U)
    {
      static      if (op == "+") __gmpz_add_ui(&z, &z, v);
      else static if (op == "-") __gmpz_sub_ui(&z, &z, v);
      else static if (op == "*") __gmpz_mul_ui(&z, &z, v);
      else static if (op == "/") __gmpz_tdiv_q_ui(&z, &z, v);
      else static if (op == "%") __gmpz_tdiv_r_ui(&z, &z, v);
      else static if (op == "^^") __gmpz_pow_ui(&z, &z, v);
      return this;
    }

    GmpInt abs() const
    {
      auto r = GmpInt(0);
      __gmpz_abs(&r.z, &z);
      return r;
    }
    GmpInt sqrt() const
    {
      auto r = GmpInt(0);
      __gmpz_sqrt(&r.z, &z);
      return r;
    }
    size_t popcnt() const
    {
      return __gmpz_popcount(&z);
    }
    bool probabPrime(int reps = 20) const
    {
      return __gmpz_probab_prime_p(&z, reps) != 0;
    }
  }

  pure nothrow
  {
    @safe this(string s, int base = 10)
    {
      __gmpz_init_set_str(&z, s.toStringz, base);
    }
    @trusted string toString(int base = 10) const
    {
      auto sz = __gmpz_sizeinbase(&z, base);
      auto buf = new char[](sz + 2);
      __gmpz_get_str(buf.ptr, base, &z);
      return buf.ptr.fromStringz.to!string;
    }
  }

  size_t fprint(File f, int base = 10) const
  {
    return __gmpz_out_str(f.getFP, base, &z);
  }

  private
  {
    import std.stdio : File;
    __mpz_struct z;
  }
}

extern(C) pragma(inline, false)
{
  import core.stdc.stdio : FILE;
  alias __mp_limb_t = ulong;

  struct __mpz_struct
  {
    int _mp_alloc;
    int _mp_size;
    __mp_limb_t* _mp_d;
  }

  alias mpz_srcptr = const(__mpz_struct)*;
  alias mpz_ptr = __mpz_struct*;

  pure nothrow @nogc @safe
  {
    void __gmpz_init(mpz_ptr);
    void __gmpz_clear(mpz_ptr);

    void __gmpz_init_set(mpz_ptr, mpz_srcptr);
    void __gmpz_init_set_si(mpz_ptr, long);
    int __gmpz_init_set_str(mpz_ptr, const char*, int);

    void __gmpz_set(mpz_ptr, mpz_srcptr);
    void __gmpz_set_si(mpz_ptr, long);

    long __gmpz_get_si(mpz_srcptr);
    char *__gmpz_get_str(char*, int, mpz_srcptr);
    size_t __gmpz_sizeinbase(mpz_srcptr, int);

    size_t __gmpz_out_str(FILE*, int, mpz_srcptr);

    int __gmpz_cmp(mpz_srcptr, mpz_srcptr);
    int __gmpz_cmp_si(mpz_srcptr, long);

    void __gmpz_add(mpz_ptr, mpz_srcptr, mpz_srcptr);
    void __gmpz_add_ui(mpz_ptr, mpz_srcptr, ulong);
    void __gmpz_sub(mpz_ptr, mpz_srcptr, mpz_srcptr);
    void __gmpz_sub_ui(mpz_ptr, mpz_srcptr, ulong);
    void __gmpz_mul(mpz_ptr, mpz_srcptr, mpz_srcptr);
    void __gmpz_mul_ui(mpz_ptr, mpz_srcptr, ulong);
    void __gmpz_tdiv_q(mpz_ptr, mpz_srcptr, mpz_srcptr);
    void __gmpz_tdiv_r(mpz_ptr, mpz_srcptr, mpz_srcptr);
    ulong __gmpz_tdiv_q_ui(mpz_ptr, mpz_srcptr, ulong);
    ulong __gmpz_tdiv_r_ui(mpz_ptr, mpz_srcptr, ulong);
    void __gmpz_pow_ui(mpz_ptr, mpz_srcptr, ulong);

    void __gmpz_abs(mpz_ptr, mpz_srcptr);
    void __gmpz_sqrt(mpz_ptr, mpz_srcptr);
    size_t __gmpz_popcount(mpz_srcptr);
    int __gmpz_probab_prime_p(mpz_srcptr, int reps);
  }
}
pragma(lib, "gmp");

auto io = IO!()();
import std.stdio;
struct IO(alias IN = stdin, alias OUT = stdout)
{
  import std.meta : allSatisfy;
  import core.stdc.stdlib : exit;

  void getV(T...)(ref T v)
  {
    foreach (ref w; v) get(w);
  }
  void getA(T)(size_t n, ref T v)
    if (hasAssignableElements!T)
  {
    v = new T(n);
    foreach (ref w; v) get(w);
  }
  void getC(T...)(size_t n, ref T v)
    if (allSatisfy!(hasAssignableElements, T))
  {
    foreach (ref w; v) w = new typeof(w)(n);
    foreach (i; 0..n) foreach (ref w; v) get(w[i]);
  }
  void getM(T)(size_t r, size_t c, ref T v)
    if (hasAssignableElements!T && hasAssignableElements!(ElementType!T))
  {
    v = new T(r);
    foreach (ref w; v) getA(c, w);
  }
  template getS(E...)
  {
    void getS(T)(size_t n, ref T v)
    {
      v = new T(n);
      foreach (ref w; v) foreach (e; E) mixin("get(w."~e~");");
    }
  }

  const struct PutConf
  {
    bool newline = true, flush, exit;
    string floatFormat = "%.10f", delimiter = " ";
  }

  void put(alias conf = "{}", T...)(T v)
  {
    mixin("const PutConf c = "~conf~"; putMain!c(v);");
  }
  void putB(alias conf = "{}", S, T)(bool c, S t, T f)
  {
    if (c) put!conf(t);
    else put!conf(f);
  }
  void putRaw(T...)(T v)
  {
    OUT.write(v);
    OUT.writeln;
  }

  private
  {
    dchar[] buf;
    auto sp = (new dchar[](0)).splitter;

    void nextLine()
    {
      IN.readln(buf);
      sp = buf.splitter;
    }
    void get(T)(ref T v)
    {
      if (sp.empty) nextLine();
      v = sp.front.to!T;
      sp.popFront();
    }

    void putMain(PutConf c, T...)(T v)
    {
      foreach (i, w; v) {
        putOne!c(w);
        if (i+1 < v.length) OUT.write(c.delimiter);
      }
      static if (c.newline) OUT.writeln;
      static if (c.flush) OUT.flush();
      static if (c.exit) exit(0);
    }
    void putOne(PutConf c, T)(T v)
    {
      static if (isInputRange!T && !isSomeString!T) putRange!c(v);
      else static if (isFloatingPoint!T) OUT.write(format(c.floatFormat, v));
      else static if (hasMember!(T, "fprint")) v.fprint(OUT);
      else OUT.write(v);
    }
    void putRange(PutConf c, T)(T v)
    {
      auto w = v;
      while (!w.empty) {
        putOne!c(w.front); w.popFront();
        if (!w.empty) OUT.write(c.delimiter);
      }
    }
  }
}