Submission #28804079

---

Source Code Expand

import std.algorithm, std.array, std.container, std.conv, std.math, std.numeric, std.random, std.range, std.stdio, std.string, std.typecons, core.bitop;

const int  max_n = 16;
const int  number_of_trials = 30000000;
const bool replace_default_prng_implementation = false;

void main()
{
  static if (replace_default_prng_implementation) {
    // Use JSF32 instead of Mersenne Twister
    auto rng = Jsf32(unpredictableSeed);
    // Replace uniform function
    uint uniform(const uint lb, const uint ub) { return lb + bounded_rand(ub - lb, rng); }
  }

  // Process input
  auto n = readln.strip.to!uint;
  assert(n <= max_n);
  int[max_n * 2][max_n * 2] a;
  foreach (row ; 0 .. 2 * n - 1) {
    foreach (col ; 2 * n - (2 * n - 1 - row) .. 2 * n) {
      readf!" %d "(a[row][col]);
      a[col][row] = a[row][col];
    }
  }

  auto p = iota(2 * n).array;

  // Calculate XOR value for the initial permutation
  int cur_xor = 0;
  foreach (k ; 0 .. p.length / 2) {
    auto i = p[k * 2 + 0];
    auto j = p[k * 2 + 1];
    cur_xor ^= a[i][j];
  }
  int best_xor = cur_xor;

  // Now try random permutations
  foreach (trial ; 0 .. number_of_trials) {
    // Pick two random indexes to swap
    auto idx1 = uniform(0, 2 * n);
    auto idx2 = uniform(0, 2 * n - 1);
    idx2 += (idx2 >= idx1) ? 1 : 0;

    // Undo XOR, swap and re-apply XOR
    cur_xor ^= a[p[idx1]][p[idx1 ^ 1]];
    cur_xor ^= a[p[idx2]][p[idx2 ^ 1]];
    swap(p[idx1], p[idx2]);
    cur_xor ^= a[p[idx1]][p[idx1 ^ 1]];
    cur_xor ^= a[p[idx2]][p[idx2 ^ 1]];

    best_xor = max(best_xor, cur_xor);
  }
  writeln(best_xor);
}

// From: https://www.pcg-random.org/posts/bounded-rands.html
uint bounded_rand(UniformRNG)(const uint range, ref UniformRNG rng)
{
  ulong x = std.random.uniform!uint(rng);
  ulong m = x * range;
  uint  l = cast(uint)m;
  if (l < range) {
    uint t = -range;
    if (t >= range) {
      t -= range;
      if (t >= range)
        t %= range;
    }
    while (l < t) {
      x = std.random.uniform!uint(rng);
      m = x * range;
      l = cast(uint)m;
    }
  }
  return m >> 32;
}

// From: https://www.pcg-random.org/posts/bounded-rands.html
uint biased_bounded_rand(UniformRNG)(const uint range, ref UniformRNG rng)
{
  return (cast(ulong)std.random.uniform!uint(rng) * range) >> 32;
}

// From: https://burtleburtle.net/bob/rand/smallprng.html
struct JsfEngine(UIntType)
{
  public:
    /// Mark this as a Rng
    enum bool isUniformRandom = true;
    /// Always `false` (random generators are infinite ranges).
    enum empty = false;
    /// Smallest generated value.
    enum UIntType min = UIntType.min;
    /// Largest generated value.
    enum UIntType max = UIntType.max;

  private:
    struct ranctx { UIntType a; UIntType b; UIntType c; UIntType d; }
    ranctx ctx;

    UIntType rot(UIntType x, int k) { return (((x)<<(k))|((x)>>(32-(k)))); }

    UIntType ranval(ref ranctx x)
    {
      UIntType e = x.a - rot(x.b, 27);
      x.a = x.b ^ rot(x.c, 17);
      x.b = x.c + x.d;
      x.c = x.d + e;
      x.d = e + x.a;
      return x.d;
    }

    void raninit(ref ranctx x, UIntType seed)
    {
      x.a = 0xf1ea5eed; x.b = x.c = x.d = seed;
      for (int i = 0; i < 21; ++i)
        ranval(x);
    }

  public:

    this()(UIntType x0) @safe pure nothrow @nogc { seed(x0); }

    void seed()(UIntType x0) @safe pure nothrow @nogc { raninit(ctx, x0); }

    @property
    UIntType front() const @safe pure nothrow @nogc { return ctx.d; }

    void popFront() @safe pure nothrow @nogc { ranval(ctx); }

    @property
    typeof(this) save() const @safe pure nothrow @nogc { return this; }
}

alias Jsf32 = JsfEngine!(uint);

Submission Info

Judge Result