結果

問題 No.624 Santa Claus and The Last Dungeon
コンテスト
ユーザー hos.lyric
提出日時 2020-04-01 17:35:48
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 64 ms / 2,000 ms
コード長 4,534 bytes
コンパイル時間 866 ms
コンパイル使用メモリ 129,540 KB
実行使用メモリ 25,208 KB
平均クエリ数 406.78
最終ジャッジ日時 2024-06-22 06:21:46
合計ジャッジ時間 5,594 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, 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)); }

uint xrand() {
  static uint x = 314159265, y = 358979323, z = 846264338, w = 327950288;
  uint t = x ^ x << 11; x = y; y = z; z = w; return w = w ^ w >> 19 ^ t ^ t >> 8;
}

enum N = 10;

debug {
  int[] A, B;
}

int numAsks;
int[] Ask(int[] as, int[] bs) {
  ++numAsks;
  auto ret = new int[3];
  debug {
    foreach (i; 0 .. N^^2) {
      ++ret[((A[i] == as[i]) ? 1 : 0) + ((B[i] == bs[i]) ? 1 : 0)];
    }
  } else {
    foreach (i; 0 .. N^^2) {
      if (i > 0) write(" ");
      (as[i] == -1) ? write('?') : write(as[i]);
      (bs[i] == -1) ? write('?') : write(bs[i]);
    }
    writeln();
    stdout.flush;
    foreach (j; 0 .. 3) {
      ret[j] = readInt();
    }
  }
  if (ret == [0, 0, N^^2]) {
    debug {
      writeln("OK numAsks = ", numAsks);
    }
    import core.stdc.stdlib;
    exit(0);
  }
  return ret;
}

alias Result = Tuple!(int[], "found", int[], "remaining");

Result solveA(int[] xs, int a, int k) {
  const len = cast(int)(xs.length);
  assert(0 <= k && k <= len);
  if (k == 0) {
    return Result([], xs);
  }
  if (k == len) {
    return Result(xs, []);
  }
  auto xss = new int[][2];
  foreach (i; 0 .. len) {
    xss[i % 2] ~= xs[i];
  }
  auto as = new int[N^^2];
  auto bs = new int[N^^2];
  as[] = -1;
  bs[] = -1;
  foreach (x; xss[1]) {
    as[x] = a;
  }
  const res = Ask(as, bs);
  auto res0 = solveA(xss[0], a, k - res[1]);
  auto res1 = solveA(xss[1], a, res[1]);
  return Result(res0.found ~ res1.found, res0.remaining ~ res1.remaining);
}

Result solveB(int[] xs, int a, int b) {
  const len = cast(int)(xs.length);
  assert(0 <= 1 && 1 <= len);
  if (1 == len) {
    return Result(xs, []);
  }
  auto xss = new int[][3];
  foreach (i; 0 .. len) {
    xss[i % 3] ~= xs[i];
  }
  auto as = new int[N^^2];
  auto bs = new int[N^^2];
  as[] = -1;
  bs[] = -1;
  foreach (x; xss[2]) {
    as[x] = a;
    bs[x] = b;
  }
  foreach (x; xss[1]) {
    bs[x] = b;
  }
  const res = Ask(as, bs);
  if (res[2] >= 1) {
    auto res2 = solveB(xss[2], a, b);
    return Result(res2.found, xss[0] ~ xss[1] ~ res2.remaining);
  } else if (res[1] >= 1 + xss[2].length) {
    auto res1 = solveB(xss[1], a, b);
    return Result(res1.found, xss[0] ~ res1.remaining ~ xss[2]);
  } else {
    auto res0 = solveB(xss[0], a, b);
    return Result(res0.found, res0.remaining ~ xss[1] ~ xss[2]);
  }
}

void main() {
  debug {
    A = new int[N^^2];
    B = new int[N^^2];
    foreach (i; 0 .. N^^2) {
      A[i] = i / N;
      B[i] = i % N;
    }
    foreach (i; 0 .. N^^2) {
      const j = cast(int)(xrand() % (i + 1));
      swap(A[j], A[i]);
      swap(B[j], B[i]);
    }
    writeln("A = ", A);
    writeln("B = ", B);
  } else {
    readInt();
  }
  
  auto xs = iota(N^^2).array;
  auto yss = new int[][N];
  foreach (a; 0 .. N) {
    auto res = solveA(xs, a, N);
    yss[a] = res.found;
    xs = res.remaining;
  }
  debug {
    writeln("numAsks = ", numAsks);
    foreach (a; 0 .. N) {
      writefln("yss[%s] = %s", a, yss[a]);
    }
  }
  assert(xs == []);
  
  auto ansA = new int[N^^2];
  auto ansB = new int[N^^2];
  ansA[] = -1;
  ansB[] = -1;
  foreach (a; 0 .. N) {
    auto ys = yss[a];
    foreach (b; 0 .. N) {
      auto res = solveB(ys, a, b);
      assert(res.found.length == 1);
      ansA[res.found[0]] = a;
      ansB[res.found[0]] = b;
      ys = res.remaining;
    }
    assert(ys == []);
  }
  Ask(ansA, ansB);
}
0