結果

問題 No.2496 LCM between Permutations
ユーザー 👑 hos.lyrichos.lyric
提出日時 2023-10-06 22:34:22
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 121 ms / 2,000 ms
コード長 4,044 bytes
コンパイル時間 3,966 ms
コンパイル使用メモリ 156,032 KB
実行使用メモリ 25,220 KB
平均クエリ数 953.86
最終ジャッジ日時 2024-07-26 16:40:13
合計ジャッジ時間 5,201 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 24 ms
24,940 KB
testcase_01 AC 20 ms
24,964 KB
testcase_02 AC 20 ms
24,836 KB
testcase_03 AC 18 ms
25,220 KB
testcase_04 AC 20 ms
24,848 KB
testcase_05 AC 19 ms
24,836 KB
testcase_06 AC 20 ms
25,220 KB
testcase_07 AC 20 ms
24,580 KB
testcase_08 AC 20 ms
25,220 KB
testcase_09 AC 20 ms
24,836 KB
testcase_10 AC 20 ms
25,220 KB
testcase_11 AC 19 ms
24,808 KB
testcase_12 AC 18 ms
24,580 KB
testcase_13 AC 19 ms
24,964 KB
testcase_14 AC 19 ms
24,964 KB
testcase_15 AC 26 ms
24,556 KB
testcase_16 AC 27 ms
24,812 KB
testcase_17 AC 30 ms
25,184 KB
testcase_18 AC 93 ms
25,220 KB
testcase_19 AC 73 ms
24,580 KB
testcase_20 AC 99 ms
24,836 KB
testcase_21 AC 86 ms
25,220 KB
testcase_22 AC 78 ms
24,580 KB
testcase_23 AC 107 ms
25,220 KB
testcase_24 AC 89 ms
24,836 KB
testcase_25 AC 121 ms
24,964 KB
testcase_26 AC 116 ms
25,196 KB
testcase_27 AC 114 ms
24,812 KB
testcase_28 AC 117 ms
25,196 KB
権限があれば一括ダウンロードができます

ソースコード

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 counter;
int Ask(int i, int j) {
  ++counter;
  if (counter > 3 * N) {
    assert(false);
  }
  debug {
    const l = lcm(A[i], B[j]);
    if (N <= 10) {
      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;
  debug {
    assert(A == as);
    assert(B == bs);
  }
  import core.stdc.stdlib;
  exit(0);
}

void main() {
  N = readInt;
  debug {
    A = iota(1, N + 1).array;
    B = iota(1, N + 1).array;
    xrand;
    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) {
    int rem;
    foreach (i; 0 .. N - 1) {
      const res = Ask(i, jm);
      if (res == P) {
        if (rem) {
          as[i] = rem;
        } else {
          const res1 = Ask(i, (jm + 1) % N);
          if (res1 % P == 0) {
            as[i] = P;
            rem = 1;
          } else {
            as[i] = 1;
            rem = P;
          }
        }
      } else {
        as[i] = res / P;
      }
    }
    as[N - 1] = N * (N + 1) / 2 - as[0 .. N - 1].sum;
  }
  void checkB(int im) {
    int rem;
    foreach (j; 0 .. N - 1) {
      const res = Ask(im, j);
      if (res == P) {
        if (rem) {
          bs[j] = rem;
        } else {
          const res1 = Ask((im + 1) % N, j);
          if (res1 % P == 0) {
            bs[j] = P;
            rem = 1;
          } else {
            bs[j] = 1;
            rem = P;
          }
        }
      } 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