結果

問題 No.97 最大の値を求めるくえり
ユーザー te-shte-sh
提出日時 2017-04-21 12:18:43
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 524 ms / 5,000 ms
コード長 1,280 bytes
コンパイル時間 745 ms
コンパイル使用メモリ 89,900 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-03 12:55:21
合計ジャッジ時間 5,929 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 3 ms
4,384 KB
testcase_02 AC 178 ms
4,380 KB
testcase_03 AC 176 ms
4,380 KB
testcase_04 AC 53 ms
4,384 KB
testcase_05 AC 57 ms
4,380 KB
testcase_06 AC 59 ms
4,376 KB
testcase_07 AC 72 ms
4,376 KB
testcase_08 AC 84 ms
4,376 KB
testcase_09 AC 109 ms
4,380 KB
testcase_10 AC 154 ms
4,376 KB
testcase_11 AC 203 ms
4,376 KB
testcase_12 AC 250 ms
4,376 KB
testcase_13 AC 295 ms
4,376 KB
testcase_14 AC 524 ms
4,380 KB
testcase_15 AC 83 ms
4,380 KB
testcase_16 AC 80 ms
4,376 KB
testcase_17 AC 77 ms
4,380 KB
testcase_18 AC 76 ms
4,384 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.algorithm, std.conv, std.range, std.stdio, std.string;

void main()
{
  auto rd = readln.split.to!(int[]), n = rd[0], qn = rd[1];
  auto ai = generateA(n);

  if (n < 3000) {
    calc1(ai, qn);
  } else {
    calc2(ai, qn);
  }
}

void calc1(long[] ai, int qn)
{
  foreach (_; 0..qn) {
    auto q = readln.chomp.to!long;
    writeln(ai.map!(a => a * q % p).maxElement);
  }
}

void calc2(long[] ai, int qn)
{
  auto bi = new bool[](p);
  foreach (a; ai) bi[a] = true;

  foreach (_; 0..qn) {
    auto q = readln.chomp.to!long;

    if (q == 0) {
      writeln(0);
    } else {
      long qi, d;
      exEuclid(q, p, qi, d);
      foreach_reverse (m; 0..p) {
        auto i = ((m * qi) % p + p) % p;
        if (bi[i]) {
          writeln(m);
          break;
        }
      }
    }
  }
}

const p = 100003;

uint x = 123456789, y = 362436069, z = 521288629, w = 88675123;
uint xor128()
{
  uint t = x ^ (x << 11);
  x = y; y = z; z = w;
  return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
}

long[] generateA(int n)
{
  auto ai = new long[](n);
  foreach (i, ref a; ai)
    a = xor128 % p;
  return ai;
}

pure T exEuclid(T)(T a, T b, ref T x, ref T y)
{
  auto g = a;
  x = 1;
  y = 0;
  if (b != 0) {
    g = exEuclid(b, a % b, y, x);
    y -= a / b * x;
  }
  return g;
}
0