結果

問題 No.2496 LCM between Permutations
ユーザー hos.lyric
提出日時 2023-10-06 22:20:03
言語 D
(dmd 2.109.1)
結果
RE  
実行時間 -
コード長 3,604 bytes
コンパイル時間 2,045 ms
コンパイル使用メモリ 156,644 KB
実行使用メモリ 25,592 KB
平均クエリ数 953.86
最終ジャッジ日時 2024-07-26 16:33:21
合計ジャッジ時間 5,392 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 1
other AC * 7 RE * 21
権限があれば一括ダウンロードができます

ソースコード

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; }

string COLOR(string s = "") { return "\x1b[" ~ s ~ "m"; }

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;
}


int N;
debug {
  int[] A, B;
}

int Ask(int i, int j) {
  debug {
    const l = lcm(A[i], B[j]);
    writeln(i, " ", j, ": ", A[i], " ", B[j], "; ", l);
    return l;
  } else {
    writefln("? %s %s", i + 1, j + 1);
    stdout.flush;
    const l = readInt;
    return l;
  }
}
void Answer(int[] as, int[] bs) {
  write("!");
  foreach (i; 0 .. N) write(" ", as[i]);
  foreach (j; 0 .. N) write(" ", bs[j]);
  writeln;
  stdout.flush;
  import core.stdc.stdlib;
  exit(0);
}

void main() {
  N = readInt;
  debug {
    A = iota(1, N + 1).array;
    B = iota(1, N + 1).array;
    foreach (i; 0 .. N) swap(A[xrand() % (i + 1)], A[i]);
    foreach (i; 0 .. N) swap(B[xrand() % (i + 1)], B[i]);
    writeln("A = ", A);
    writeln("B = ", B);
  }
  
  auto lpf = iota(N + 1).array;
  int P;
  for (int p = 2; p <= N; ++p) if (lpf[p] == p) {
    chmax(P, p);
    for (int n = 2 * p; n <= N; n += p) chmin(lpf[n], p);
  }
  
  auto as = new int[N];
  auto bs = new int[N];
  void checkA(int jm) {
    foreach (i; 0 .. N - 1) {
      const res = Ask(i, jm);
      if (res == P) {
        const res1 = Ask(i, (jm + 1) % N);
        if (res1 % P == 0) {
          as[i] = P;
        } else {
          as[i] = 1;
        }
      } else {
        as[i] = res / P;
      }
    }
    as[N - 1] = N * (N + 1) / 2 - as[0 .. N - 1].sum;
  }
  void checkB(int im) {
    foreach (j; 0 .. N - 1) {
      const res = Ask(im, j);
      if (res == P) {
        const res1 = Ask((im + 1) % N, j);
        if (res1 % P == 0) {
          bs[j] = P;
        } else {
          bs[j] = 1;
        }
      } else {
        bs[j] = res / P;
      }
    }
    bs[N - 1] = N * (N + 1) / 2 - bs[0 .. N - 1].sum;
  }
  
  if (N == 1) {
    as[0] = 1;
    bs[0] = 1;
  } else {
    auto cs = new int[N];
    foreach (j; 0 .. N) cs[j] = Ask(0, j);
    int jm = -1;
    foreach (j; 0 .. N) if (cs[j] % P == 0) {
      if (jm != -1) jm = -2;
      if (jm == -1) jm = j;
    }
    if (jm == -2) {
      // A[0] = p
      checkB(0);
      jm = -1;
      foreach (j; 0 .. N) if (bs[j] == P) jm = j;
      checkA(jm);
    } else {
      // B[jm] = p
      checkA(jm);
      int im = -1;
      foreach (i; 0 .. N) if (as[i] == P) im = i;
      checkB(im);
    }
  }
  Answer(as, bs);
}
0