結果

問題 No.387 ハンコ
コンテスト
ユーザー te-sh
提出日時 2017-07-25 17:56:16
言語 D
(dmd 2.109.1)
結果
MLE  
実行時間 -
コード長 2,812 bytes
コンパイル時間 977 ms
コンパイル使用メモリ 102,808 KB
実行使用メモリ 812,744 KB
最終ジャッジ日時 2024-06-12 21:12:21
合計ジャッジ時間 4,158 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other MLE * 1 -- * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.algorithm, std.conv, std.range, std.stdio, std.string;
import std.bitmanip;  // BitArray

void main()
{
  auto n = readln.chomp.to!size_t, n2 = n * 2 - 1;

  auto newBitArray(size_t n) {
    return GmpBit(n);
  }

  auto a = new int[](n), rda = readln.chomp.splitter;
  foreach (i; 0..n) {
    a[i] = rda.front.to!int;
    rda.popFront();
  }

  auto b = newBitArray(n2), rdb = readln.chomp.splitter;
  foreach (i; 0..n) {
    b[i] = rdb.front.to!int.to!bool;
    rdb.popFront();
  }

  size_t[][int] c;
  foreach (i, ai; a) c[ai] ~= i;

  auto r = newBitArray(n2);
  foreach (ci; c.byValue) {
    auto d = newBitArray(n2);
    foreach (cii; ci)
      d |= b << cii;
    r ^= d;
  }

  foreach (i; 0..2*n-1)
    writeln(r[i] ? "ODD" : "EVEN");
}

struct GmpBit
{
  __mpz_struct z;
  size_t n;

  this(size_t n)
  {
    this.n = n;
    __gmpz_init2(&z, n);
  }

  auto opIndex(size_t i)
  {
    return __gmpz_tstbit(&z, i) != 0;
  }

  auto opIndexAssign(bool v, size_t i)
  {
    if (v) __gmpz_setbit(&z, i);
    else   __gmpz_clrbit(&z, i);
  }

  auto opBinary(string op)(GmpBit v)
    if (op == "&" || op == "|" || op == "^")
  {
    auto r = GmpBit(n);
    static if (op == "&") __gmpz_and(&r.z, &z, &v.z);
    else   if (op == "|") __gmpz_ior(&r.z, &z, &v.z);
    else   if (op == "^") __gmpz_xor(&r.z, &z, &v.z);
    return r;
  }

  auto opBinary(string op)(size_t m)
    if (op == "<<" || op == ">>")
  {
    auto r = GmpBit(n);
    static if (op == "<<") __gmpz_mul_2exp(&r.z, &z, m);
    else   if (op == ">>") __gmpz_tdiv_q_2exp(&r.z, &z, m);
    return r;
  }

  auto opOpAssign(string op)(GmpBit v)
    if (op == "&" || op == "|" || op == "^")
  {
    static if (op == "&") __gmpz_and(&z, &z, &v.z);
    else   if (op == "|") __gmpz_ior(&z, &z, &v.z);
    else   if (op == "^") __gmpz_xor(&z, &z, &v.z);
  }

  auto opOpAssign(string op)(size_t n)
    if (op == "<<" || op == ">>")
  {
    static if (op == "<<") __gmpz_mul_2exp(&z, &z, m);
    else   if (op == ">>") __gmpz_tdiv_q_2exp(&z, &z, m);
  }

  size_t popcnt()
  {
    return __gmpz_popcount(&z);
  }
}

extern(C) pragma(inline, false)
{
  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*;

  void __gmpz_init2(mpz_ptr, size_t);

  void __gmpz_setbit(mpz_ptr, size_t i);
  void __gmpz_clrbit(mpz_ptr, size_t i);
  int __gmpz_tstbit(mpz_ptr, size_t i);

  void __gmpz_and(mpz_ptr, mpz_srcptr, mpz_srcptr);
  void __gmpz_ior(mpz_ptr, mpz_srcptr, mpz_srcptr);
  void __gmpz_xor(mpz_ptr, mpz_srcptr, mpz_srcptr);

  void __gmpz_mul_2exp(mpz_ptr, mpz_srcptr, size_t);
  void __gmpz_tdiv_q_2exp(mpz_ptr, mpz_srcptr, size_t);

  size_t __gmpz_popcount(mpz_srcptr);
}

pragma(lib, "gmp");
0