Submission #72327043

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

static constexpr int N = 20;
static constexpr int MAX_OPS = 2 * N * N * N; // 16000

// ---------------- RNG ----------------
struct XorShift64 {
  uint64_t x = 88172645463393265ull;
  inline uint64_t next_u64() {
    x ^= x << 7;
    x ^= x >> 9;
    return x;
  }
  inline uint32_t next_u32() { return (uint32_t)next_u64(); }
  inline int next_int(int lo, int hi) {
    return lo + (int)(next_u32() % (uint32_t)(hi - lo + 1));
  }
  inline double next_double01() {
    return (next_u64() >> 11) * (1.0 / 9007199254740992.0);
  }
};

struct Timer {
  using clk = chrono::steady_clock;
  clk::time_point st;
  Timer() : st(clk::now()) {}
  inline double sec() const {
    return chrono::duration<double>(clk::now() - st).count();
  }
};

struct Pt {
  int r, c;
};
static inline int manhattan(const Pt &a, const Pt &b) {
  return abs(a.r - b.r) + abs(a.c - b.c);
}
static inline long long penalty_ops(long long total_ops) {
  if (total_ops <= MAX_OPS)
    return 0LL;
  return (total_ops - MAX_OPS) * 1000000LL;
}

// ---------------- State ----------------
struct State {
  int M = 0;
  vector<Pt> p0, p1;

  int root;               // = M
  vector<int> parent;     // size M+1
  vector<vector<int>> ch; // size M+1
  vector<uint8_t> flip;   // size M

  long long cost = (1LL << 60);
  vector<int> seq;
  vector<Pt> visit_pts;

  long long K_move = 0;
  vector<int> open_pos, close_pos;
  bool cache_valid = false;

  void build_sequence() {
    seq.clear();
    seq.reserve(2 * M);
    struct Frame {
      int u, it;
      bool opened;
    };
    vector<Frame> st;
    st.push_back({root, 0, true});
    while (!st.empty()) {
      auto &fr = st.back();
      int u = fr.u;
      if (u != root && !fr.opened) {
        seq.push_back(+u);
        fr.opened = true;
      }
      if (fr.it < (int)ch[u].size()) {
        int v = ch[u][fr.it++];
        st.push_back({v, 0, false});
      } else {
        if (u != root)
          seq.push_back(-u - 1);
        st.pop_back();
      }
    }
  }

  void build_visit_points() {
    visit_pts.clear();
    visit_pts.reserve(2 * M);
    for (int e : seq) {
      if (e >= 0) {
        int u = e;
        visit_pts.push_back(!flip[u] ? p0[u] : p1[u]);
      } else {
        int u = -e - 1;
        visit_pts.push_back(!flip[u] ? p1[u] : p0[u]);
      }
    }
  }

  void build_open_close_pos() {
    open_pos.assign(M, -1);
    close_pos.assign(M, -1);
    for (int i = 0; i < (int)seq.size(); i++) {
      int e = seq[i];
      if (e >= 0)
        open_pos[e] = i;
      else
        close_pos[-e - 1] = i;
    }
  }

  long long compute_K_move() const {
    Pt cur{0, 0};
    long long K = 0;
    for (const auto &p : visit_pts) {
      K += manhattan(cur, p);
      cur = p;
    }
    return K;
  }

  long long eval_cost_full() {
    build_sequence();
    if ((int)seq.size() != 2 * M) {
      cost = (1LL << 60);
      cache_valid = false;
      return cost;
    }
    build_visit_points();
    build_open_close_pos();
    K_move = compute_K_move();
    long long Zcnt = 2LL * M; // baseline: take only
    cost = K_move + penalty_ops(K_move + Zcnt);
    cache_valid = true;
    return cost;
  }

  inline long long edge_dist_idx(int idx) const {
    if (idx == -1)
      return manhattan(Pt{0, 0}, visit_pts[0]);
    return manhattan(visit_pts[idx], visit_pts[idx + 1]);
  }

  void apply_flip_delta(int u) {
    int i = open_pos[u];
    int j = close_pos[u];
    if (i < 0 || j < 0 || i == j) {
      flip[u] ^= 1;
      (void)eval_cost_full();
      return;
    }
    if (i > j)
      swap(i, j);

    const int L = (int)visit_pts.size();
    int cand[4] = {i - 1, i, j - 1, j};
    int edges[4];
    int ec = 0;
    for (int t = 0; t < 4; t++) {
      int k = cand[t];
      if (k < -1)
        continue;
      if (k > L - 2)
        continue;
      edges[ec++] = k;
    }
    sort(edges, edges + ec);
    ec = (int)(unique(edges, edges + ec) - edges);

    long long before = 0;
    for (int t = 0; t < ec; t++)
      before += edge_dist_idx(edges[t]);

    flip[u] ^= 1;
    swap(visit_pts[i], visit_pts[j]);

    long long after = 0;
    for (int t = 0; t < ec; t++)
      after += edge_dist_idx(edges[t]);

    K_move += (after - before);
    long long Zcnt = 2LL * M;
    cost = K_move + penalty_ops(K_move + Zcnt);
  }

  bool is_ancestor(int a, int b) const {
    int x = b;
    while (x != -1 && x != root) {
      if (x == a)
        return true;
      x = parent[x];
    }
    return (a == root);
  }

  int index_in_children(int par, int u) const {
    const auto &v = ch[par];
    for (int i = 0; i < (int)v.size(); i++)
      if (v[i] == u)
        return i;
    return -1;
  }

  void erase_child(int par, int idx) {
    auto &v = ch[par];
    v.erase(v.begin() + idx);
  }
  void insert_child(int par, int idx, int u) {
    auto &v = ch[par];
    v.insert(v.begin() + idx, u);
  }
  static inline long long distPt(const Pt &a, const Pt &b) {
    return (long long)abs(a.r - b.r) + (long long)abs(a.c - b.c);
  }

  static inline Pt START_PT() { return Pt{0, 0}; }

  // vp の「辺」を加算（左端は START から）
  static inline long long edge_between(const vector<Pt> &vp, int left_idx) {
    // left_idx = -1 means START -> vp[0]
    if (left_idx == -1)
      return distPt(START_PT(), vp[0]);
    return distPt(vp[left_idx], vp[left_idx + 1]);
  }
  void rebuild_open_close_pos_from_seq() {
    open_pos.assign(M, -1);
    close_pos.assign(M, -1);
    for (int i = 0; i < (int)seq.size(); i++) {
      int e = seq[i];
      if (e >= 0)
        open_pos[e] = i;
      else
        close_pos[-e - 1] = i;
    }
  }
  int compute_insert_pos_in_seq(int new_par, int new_idx) const {
    // NOTE: ch[new_par] は「変更後（u を挿入済み）」の状態を想定してOK。
    // ここでは new_idx の位置に u が入っている前提ではなく、
    // 「u を挿入する位置 new_idx」を受け取る想定で書くのが扱いやすい。
    // なので、呼び出し側で "挿入前の new_idx" を渡すのが安全。

    if (new_par == root) {
      // root は open/close が seq に存在しない
      if (new_idx >= (int)ch[root].size())
        return (int)seq.size();
      int v = ch[root][new_idx];
      return open_pos[v]; // v の subtree の先頭
    } else {
      if (new_idx >= (int)ch[new_par].size()) {
        // parent の close の直前が末尾
        return close_pos[new_par];
      } else {
        int v = ch[new_par][new_idx];
        return open_pos[v];
      }
    }
  }
  bool apply_repar_fast(int u, int old_par, int old_idx, int new_par,
                        int new_idx) {
    // 前提: cache_valid=true で seq/visit_pts/open_pos/close_pos/K_move
    // が正しいこと
    int l = open_pos[u];
    int r = close_pos[u];
    if (l < 0 || r < 0 || l >= r)
      return false;

    // ---- old boundary points (before cut) ----
    Pt A = (l == 0 ? START_PT() : visit_pts[l - 1]);
    Pt B = visit_pts[l];
    Pt C = visit_pts[r];
    bool hasD = (r + 1 < (int)visit_pts.size());
    Pt D = hasD ? visit_pts[r + 1] : Pt{-1, -1};

    long long K_before = K_move;

    // ---- cut segment out from seq & visit_pts ----
    const int segLen = r - l + 1;

    vector<int> seg_seq(seq.begin() + l, seq.begin() + r + 1);
    vector<Pt> seg_vp(visit_pts.begin() + l, visit_pts.begin() + r + 1);

    seq.erase(seq.begin() + l, seq.begin() + r + 1);
    visit_pts.erase(visit_pts.begin() + l, visit_pts.begin() + r + 1);

    // ここで open/close が古いので作り直す（400要素）
    rebuild_open_close_pos_from_seq();

    // ---- compute insertion position in the "cut" sequence ----
    // 重要：new_idx は「挿入前」を渡すべき（呼び出し側で調整）
    int ins = compute_insert_pos_in_seq(new_par, new_idx);
    // ins は [0..seq.size()] の範囲

    // insertion boundary in cut-state
    Pt P = (ins == 0 ? START_PT() : visit_pts[ins - 1]);
    bool hasQ = (ins < (int)visit_pts.size());
    Pt Q = hasQ ? visit_pts[ins] : Pt{-1, -1};

    // ---- splice insert segment ----
    seq.insert(seq.begin() + ins, seg_seq.begin(), seg_seq.end());
    visit_pts.insert(visit_pts.begin() + ins, seg_vp.begin(), seg_vp.end());

    // open/close を再構築（400要素）
    rebuild_open_close_pos_from_seq();

    // ---- K_move delta (O(1) edges) ----
    // Old edges removed:
    //   A-B always exists
    //   C-D exists only if hasD
    // After cut, at old location A connects to D (if hasD)
    // In insertion place, edge P-Q existed only if hasQ
    // After insertion, edges P-B and C-Q (if hasQ)

    long long K = K_before;

    // remove old boundary edges
    K -= distPt(A, B);
    if (hasD)
      K -= distPt(C, D);

    // add edge bridging cut location
    if (hasD)
      K += distPt(A, D);

    // remove edge at insertion gap
    if (hasQ)
      K -= distPt(P, Q);

    // add edges with inserted segment
    K += distPt(P, B);
    if (hasQ)
      K += distPt(C, Q);

    K_move = K;

    // ---- cost update ----
    long long Zcnt = 2LL * M;
    cost = K_move + penalty_ops(K_move + Zcnt);
    cache_valid = true;
    return true;
  } // State 内に追加（helper）:
  int insert_pos_by_before_v(int par_ins, int before_v) const {
    // par_ins: insert into this parent
    // before_v: the child that should come right after u (insert before it). -1
    // means append at end.
    if (before_v != -1) {
      // insert before that subtree's first token
      return open_pos[before_v];
    }
    // append
    if (par_ins == root)
      return (int)seq.size();
    return close_pos[par_ins]; // insert before parent's close
  }

  // State 内に追加（REPAR fast 本体）
  bool apply_repar_fast_beforev(int u, int par_ins, int before_v) {
    // 前提: cache_valid=true, seq/visit_pts/open_pos/close_pos/K_move が整合
    int l = open_pos[u];
    int r = close_pos[u];
    if (l < 0 || r < 0 || l >= r)
      return false;

    // --- old boundary (cut) ---
    Pt A = (l == 0 ? Pt{0, 0} : visit_pts[l - 1]);
    Pt B = visit_pts[l];
    Pt C = visit_pts[r];
    bool hasD = (r + 1 < (int)visit_pts.size());
    Pt D = hasD ? visit_pts[r + 1] : Pt{-1, -1};

    long long K_before = K_move;

    // cut segment
    vector<int> seg_seq(seq.begin() + l, seq.begin() + r + 1);
    vector<Pt> seg_vp(visit_pts.begin() + l, visit_pts.begin() + r + 1);

    seq.erase(seq.begin() + l, seq.begin() + r + 1);
    visit_pts.erase(visit_pts.begin() + l, visit_pts.begin() + r + 1);

    // rebuild open/close for "cut" state
    rebuild_open_close_pos_from_seq();

    // compute insertion index in cut-state
    int ins = insert_pos_by_before_v(par_ins, before_v);

    // insertion boundary
    Pt P = (ins == 0 ? Pt{0, 0} : visit_pts[ins - 1]);
    bool hasQ = (ins < (int)visit_pts.size());
    Pt Q = hasQ ? visit_pts[ins] : Pt{-1, -1};

    // splice insert segment
    seq.insert(seq.begin() + ins, seg_seq.begin(), seg_seq.end());
    visit_pts.insert(visit_pts.begin() + ins, seg_vp.begin(), seg_vp.end());

    // rebuild open/close for final state
    rebuild_open_close_pos_from_seq();

    // --- K_move delta (O(1)) ---
    long long K = K_before;

    // remove A-B and C-D
    K -= manhattan(A, B);
    if (hasD)
      K -= manhattan(C, D);

    // add A-D bridge
    if (hasD)
      K += manhattan(A, D);

    // remove P-Q gap edge
    if (hasQ)
      K -= manhattan(P, Q);

    // add P-B and C-Q
    K += manhattan(P, B);
    if (hasQ)
      K += manhattan(C, Q);

    K_move = K;

    long long Zcnt = 2LL * M;
    cost = K_move + penalty_ops(K_move + Zcnt);
    cache_valid = true;
    return true;
  }
};

// ---------------- SA Moves ----------------
enum MoveType { REPAR = 0, SWAP_SIB = 1, FLIP = 2 };
struct Move {
  MoveType type;
  int u = -1;
  int old_par = -1, old_idx = -1;
  int new_par = -1, new_idx = -1;

  // REPAR fast 用：
  int old_before_v = -1; // u を元に戻す時「この子の前」に挿入（-1なら末尾）
  int new_before_v = -1; // u を新しい親へ移す時「この子の前」に挿入

  int par = -1;
  int i = -1, j = -1;
};

static inline double acceptance_prob(long long delta, double T) {
  return exp(-(double)delta / T);
}

// ---------------- Path helpers ----------------
static inline void enumerate_path_cells_vh(const Pt &from, const Pt &to,
                                           vector<Pt> &cells) {
  cells.clear();
  Pt cur = from;
  int dr = to.r - cur.r;
  int dc = to.c - cur.c;
  if (dr < 0)
    for (int k = 0; k < -dr; k++) {
      cur.r--;
      cells.push_back(cur);
    }
  else
    for (int k = 0; k < dr; k++) {
      cur.r++;
      cells.push_back(cur);
    }
  if (dc < 0)
    for (int k = 0; k < -dc; k++) {
      cur.c--;
      cells.push_back(cur);
    }
  else
    for (int k = 0; k < dc; k++) {
      cur.c++;
      cells.push_back(cur);
    }
}

static inline char step_dir(const Pt &a, const Pt &b) {
  if (b.r == a.r - 1 && b.c == a.c)
    return 'U';
  if (b.r == a.r + 1 && b.c == a.c)
    return 'D';
  if (b.c == a.c - 1 && b.r == a.r)
    return 'L';
  if (b.c == a.c + 1 && b.r == a.r)
    return 'R';
  return '?';
}

// ---------------- Postprocess relocation (NO detour) ----------------
struct Action {
  int cell_idx; // index in cells[]
  char op;      // 'Z' take, 'X' place
};

struct PostPlan {
  vector<Pt> visit_pts;
  vector<vector<Action>> mid_actions; // per segment t
  long long Km = 0;
  long long opcnt = 0; // total ops (moves + Z/X)
  long long cost = (1LL << 60);
};

static inline long long compute_move_from_visit_pts(const vector<Pt> &vp) {
  Pt cur{0, 0};
  long long Km = 0;
  for (auto &p : vp) {
    Km += manhattan(cur, p);
    cur = p;
  }
  return Km;
}

static inline long long delta_move_change_at(const vector<Pt> &vp, int t,
                                             const Pt &X, const Pt &Y) {
  const int E = (int)vp.size();
  Pt prev = (t == 0 ? Pt{0, 0} : vp[t - 1]);
  long long before = manhattan(prev, X);
  long long after = manhattan(prev, Y);
  if (t < E - 1) {
    before += manhattan(X, vp[t + 1]);
    after += manhattan(Y, vp[t + 1]);
  }
  return after - before;
}

static inline void remove_event(vector<int> &lst, int tf) {
  auto it = lower_bound(lst.begin(), lst.end(), tf);
  if (it != lst.end() && *it == tf)
    lst.erase(it);
}

static PostPlan postprocess_relocate_no_detour(const State &best,
                                               const vector<vector<int>> &a) {
  const int M = best.M;
  const int E = 2 * M;

  // board stores original numbers; -1 empty
  vector<vector<int>> board(N, vector<int>(N, -1));
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      board[i][j] = a[i][j];

  vector<Pt> vp = best.visit_pts;

  vector<vector<vector<int>>> events_at(N, vector<vector<int>>(N));
  for (int t = 0; t < E; t++)
    events_at[vp[t].r][vp[t].c].push_back(t);
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      sort(events_at[i][j].begin(), events_at[i][j].end());

  vector<char> relocated(E, 0);
  vector<vector<Action>> mid(E);

  long long Km_cur = compute_move_from_visit_pts(vp);
  // baseline action count: moves(Km_cur) + takes(E)
  long long acts_cur = Km_cur + E;
  long long cost_cur = Km_cur + penalty_ops(acts_cur);

  vector<int> stack;
  Pt curPos{0, 0};

  for (int t = 0; t < E; t++) {
    vector<Pt> cells;
    enumerate_path_cells_vh(curPos, vp[t], cells);
    const int L = (int)cells.size(); // includes destination at index L-1 if L>0

    // empty positions on segment (current time)
    vector<int> empty_idx;
    empty_idx.reserve(L);
    for (int i = 0; i < L; i++) {
      Pt p = cells[i];
      if (board[p.r][p.c] == -1)
        empty_idx.push_back(i);
    }

    bool applied = false;

    // IMPORTANT: do NOT pick at destination cell (index L-1), because we will
    // also 'Z' at destination for event t.
    for (int i = 0; i < L - 1 && !applied; i++) {
      Pt X = cells[i];
      int val = board[X.r][X.c];
      if (val == -1)
        continue;

      // safety: picking must not cancel immediately (card disappears -> can't
      // place)
      if (!stack.empty() && stack.back() == val)
        continue;

      // find future event tf>t targeting X
      auto &lst = events_at[X.r][X.c];
      auto it = upper_bound(lst.begin(), lst.end(), t);
      int tf = -1;
      for (; it != lst.end(); ++it) {
        int cand_tf = *it;
        if (!relocated[cand_tf] && vp[cand_tf].r == X.r &&
            vp[cand_tf].c == X.c) {
          tf = cand_tf;
          break;
        }
      }
      if (tf < 0)
        continue;

      // choose placement Y among empty cells after i (can be destination too;
      // that's fine)
      long long best_cost = cost_cur;
      int best_j = -1;
      long long best_dm = 0;

      for (int jidx : empty_idx) {
        if (jidx <= i)
          continue;
        Pt Y = cells[jidx];

        long long dm = delta_move_change_at(vp, tf, X, Y);
        long long Km_new = Km_cur + dm;

        // extra actions: +2 (Z pick + X place), no extra moves
        long long acts_new = (Km_new + E) + 2;
        long long cost_new = Km_new + penalty_ops(acts_new);

        if (cost_new < best_cost) {
          best_cost = cost_new;
          best_j = jidx;
          best_dm = dm;
        }
      }

      if (best_j >= 0) {
        Pt Y = cells[best_j];

        // record mid actions
        mid[t].push_back({i, 'Z'});      // take at X
        mid[t].push_back({best_j, 'X'}); // place at Y
        sort(mid[t].begin(), mid[t].end(),
             [](const Action &a, const Action &b) {
               if (a.cell_idx != b.cell_idx)
                 return a.cell_idx < b.cell_idx;
               return a.op < b.op;
             });

        // apply relocation on board
        board[X.r][X.c] = -1;
        board[Y.r][Y.c] = val;

        // update mapping
        remove_event(events_at[X.r][X.c], tf);
        events_at[Y.r][Y.c].insert(lower_bound(events_at[Y.r][Y.c].begin(),
                                               events_at[Y.r][Y.c].end(), tf),
                                   tf);

        vp[tf] = Y;
        relocated[tf] = 1;

        // update costs
        Km_cur += best_dm;
        // actions +2
        acts_cur = (Km_cur + E) + 2 * 1; // we only keep it accurate for greedy
                                         // by bumping via +2 each time
        // But we might have multiple relocations; better accumulate:
        // Let's recompute actions later; for acceptance we can track count:
        // We'll keep a counter:
        cost_cur = best_cost;

        applied = true;
      }
    }

    // ---- simulate movement and execute mid actions (Z take / X place) ----
    sort(mid[t].begin(), mid[t].end(), [](const Action &a, const Action &b) {
      if (a.cell_idx != b.cell_idx)
        return a.cell_idx < b.cell_idx;
      return a.op < b.op;
    });
    int aptr = 0;

    for (int i = 0; i < L; i++) {
      curPos = cells[i];

      while (aptr < (int)mid[t].size() && mid[t][aptr].cell_idx == i) {
        char op = mid[t][aptr].op;
        if (op == 'Z') {
          // take: must have card
          int v = board[curPos.r][curPos.c];
          if (v == -1) {
            // invalid; ignore (but should not happen)
          } else {
            board[curPos.r][curPos.c] = -1;
            if (!stack.empty() && stack.back() == v)
              stack.pop_back();
            else
              stack.push_back(v);
          }
        } else { // 'X' place
          if (board[curPos.r][curPos.c] != -1) {
            // invalid; ignore (but should not happen)
          } else if (!stack.empty()) {
            int top = stack.back();
            stack.pop_back();
            board[curPos.r][curPos.c] = top;
          }
        }
        aptr++;
      }
    }

    // destination event t: Take with 'Z' (must have card ideally)
    curPos = vp[t];
    int v = board[curPos.r][curPos.c];
    if (v != -1) {
      board[curPos.r][curPos.c] = -1;
      if (!stack.empty() && stack.back() == v)
        stack.pop_back();
      else
        stack.push_back(v);
    } else {
      // if empty here, outputting 'Z' would cause "Take from empty cell" in
      // real judge so we should avoid such plans by not allowing picks at
      // destination. As a last-resort safety, we can "do nothing" in
      // simulation. (Output will still do 'Z', but this case should not occur
      // now.)
    }
  }

  // final exact stats
  PostPlan plan;
  plan.visit_pts = std::move(vp);
  plan.mid_actions = std::move(mid);

  plan.Km = compute_move_from_visit_pts(plan.visit_pts);

  long long extra = 0;
  for (int t = 0; t < E; t++)
    extra += (long long)plan.mid_actions[t].size();
  long long total_actions =
      plan.Km + E + extra; // moves + destination-takes + mid(Z/X)
  plan.opcnt = total_actions;
  plan.cost = plan.Km + penalty_ops(total_actions);

  // If not improved, revert
  {
    long long origKm = compute_move_from_visit_pts(best.visit_pts);
    long long origActions = origKm + E;
    long long origCost = origKm + penalty_ops(origActions);
    if (plan.cost >= origCost) {
      plan.visit_pts = best.visit_pts;
      plan.mid_actions.assign(E, {});
      plan.Km = origKm;
      plan.opcnt = origActions;
      plan.cost = origCost;
    }
  }
  return plan;
}

// Output ops with mid Z/X insertions + destination Z
static string
build_ops_with_insertions(const vector<Pt> &vp,
                          const vector<vector<Action>> &mid_actions) {
  const int E = (int)vp.size();
  string ops;
  ops.reserve(30000);

  Pt cur{0, 0};
  for (int t = 0; t < E; t++) {
    vector<Pt> cells;
    enumerate_path_cells_vh(cur, vp[t], cells);
    int L = (int)cells.size();

    vector<Action> acts = mid_actions[t];
    sort(acts.begin(), acts.end(), [](const Action &a, const Action &b) {
      if (a.cell_idx != b.cell_idx)
        return a.cell_idx < b.cell_idx;
      return a.op < b.op;
    });
    int aptr = 0;

    Pt prev = cur;
    for (int i = 0; i < L; i++) {
      Pt nxt = cells[i];
      ops.push_back(step_dir(prev, nxt));
      prev = nxt;

      while (aptr < (int)acts.size() && acts[aptr].cell_idx == i) {
        ops.push_back(acts[aptr].op); // 'Z' take or 'X' place
        aptr++;
      }
    }

    // destination action: Take with 'Z'
    ops.push_back('Z');
    cur = vp[t];
  }

  if ((int)ops.size() > MAX_OPS)
    ops.resize(MAX_OPS);
  return ops;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int Nin;
  cin >> Nin;

  vector<vector<int>> a(N, vector<int>(N));
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      cin >> a[i][j];

  // Map values to 0..M-1
  unordered_map<int, int> id;
  id.reserve(N * N * 2);

  vector<array<Pt, 2>> pos;
  vector<int> cnt;

  auto get_id = [&](int val) -> int {
    auto it = id.find(val);
    if (it != id.end())
      return it->second;
    int nid = (int)id.size();
    id.emplace(val, nid);
    pos.push_back({Pt{-1, -1}, Pt{-1, -1}});
    cnt.push_back(0);
    return nid;
  };

  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++) {
      int v = a[i][j];
      int k = get_id(v);
      if (cnt[k] < 2) {
        pos[k][cnt[k]] = Pt{i, j};
        cnt[k]++;
      }
    }

  int M = (int)id.size();

  State st;
  st.M = M;
  st.root = M;
  st.p0.resize(M);
  st.p1.resize(M);
  for (int k = 0; k < M; k++) {
    st.p0[k] = pos[k][0];
    st.p1[k] = pos[k][1];
  }
  st.parent.assign(M + 1, -1);
  st.ch.assign(M + 1, {});
  st.flip.assign(M, 0);

  // Initial forest: all nodes under root, ordered by distance from start
  vector<int> ord(M);
  iota(ord.begin(), ord.end(), 0);
  Pt start{0, 0};
  sort(ord.begin(), ord.end(), [&](int u, int v) {
    int du = min(manhattan(start, st.p0[u]), manhattan(start, st.p1[u]));
    int dv = min(manhattan(start, st.p0[v]), manhattan(start, st.p1[v]));
    return du < dv;
  });
  st.ch[st.root] = ord;
  for (int u = 0; u < M; u++)
    st.parent[u] = st.root;
  st.parent[st.root] = -1;

  for (int u = 0; u < M; u++) {
    int d0 = manhattan(start, st.p0[u]);
    int d1 = manhattan(start, st.p1[u]);
    st.flip[u] = (d1 < d0) ? 1 : 0;
  }

  long long cur = st.eval_cost_full();
  State best = st;
  long long best_cost = cur;

  XorShift64 rng;
  Timer timer;

  const double TIME_LIMIT = 1.95;
  const double T0 = 0.0;
  const double T1 = 0.0;

  auto temperature = [&](double t) -> double {
    double x = t / TIME_LIMIT;
    x = max(0.0, min(1.0, x));
    return T0 * pow(T1 / T0, x);
  };

  auto sample_move_type = [&]() -> MoveType {
    int r = rng.next_int(0, 99);
    if (r < 10)
      return FLIP;
    if (r < 20)
      return SWAP_SIB;
    return REPAR;
  };

  auto apply_move_structural = [&](State &S, Move &mv) -> bool {
    if (mv.type == SWAP_SIB) {
      for (int tries = 0; tries < 1; tries++) {
        int par = rng.next_int(0, S.M);
        if ((int)S.ch[par].size() >= 2) {
          int sz = (int)S.ch[par].size();
          int i = rng.next_int(0, sz - 1);
          int j = rng.next_int(0, sz - 1);
          if (i == j)
            continue;
          mv.par = par;
          mv.i = i;
          mv.j = j;
          swap(S.ch[par][i], S.ch[par][j]);
          S.cache_valid = false; // ここは従来通り full eval に任せる
          return true;
        }
      }
      return false;
    }

    // -------- REPAR (FAST) --------
    // cache を有効化（seq/visit_pts/open/close/K_move 必須）
    if (!S.cache_valid)
      (void)S.eval_cost_full();

    for (int tries = 0; tries < 1; tries++) {
      int u = rng.next_int(0, S.M - 1);
      int old_par = S.parent[u];
      if (old_par < 0)
        continue;

      int new_par = rng.next_int(0, S.M);
      if (new_par == u)
        continue;
      if (new_par == old_par)
        continue; // ←簡単化：同一親内の移動は別moveでやる（まずはここを禁止）
      if (new_par != S.root && S.is_ancestor(u, new_par))
        continue;

      int old_idx = S.index_in_children(old_par, u);
      if (old_idx < 0)
        continue;

      // --- “before_v” を記録 ---
      // old: 元に戻すとき old_idx の位置に戻したい
      //   => u の直後に来ていた子（old_idx+1）を覚える（末尾なら -1）
      int old_before_v = -1;
      if (old_idx + 1 < (int)S.ch[old_par].size())
        old_before_v = S.ch[old_par][old_idx + 1];

      // new: new_par の new_pos に入れたい
      //   => その位置に元々いた子を before_v とする（末尾なら -1）
      int new_pos = rng.next_int(0, (int)S.ch[new_par].size());
      int new_before_v = -1;
      if (new_pos < (int)S.ch[new_par].size())
        new_before_v = S.ch[new_par][new_pos];

      // --- 木を変更（u を old_par から外して new_par に入れる）---
      mv.u = u;
      mv.old_par = old_par;
      mv.old_idx = old_idx;
      mv.new_par = new_par;
      mv.new_idx = new_pos;
      mv.old_before_v = old_before_v;
      mv.new_before_v = new_before_v;

      S.erase_child(old_par, old_idx);
      S.insert_child(new_par, new_pos, u);
      S.parent[u] = new_par;

      // --- seq/visit_pts/K_move を fast splice で更新 ---
      bool ok = S.apply_repar_fast_beforev(u, new_par, new_before_v);
      if (!ok) {
        // 失敗時は木を戻して別試行
        int idx2 = S.index_in_children(new_par, u);
        if (idx2 >= 0)
          S.erase_child(new_par, idx2);
        S.insert_child(old_par, old_idx, u);
        S.parent[u] = old_par;
        (void)S.eval_cost_full(); // 保険（ここが頻発するなら原因を潰す）
        continue;
      }
      return true;
    }
    return false;
  };

  auto undo_move = [&](State &S, const Move &mv) {
    if (mv.type == FLIP)
      return;

    if (mv.type == SWAP_SIB) {
      swap(S.ch[mv.par][mv.i], S.ch[mv.par][mv.j]);
      S.cache_valid = false;
      return;
    }

    // -------- REPAR undo (FAST) --------
    // cache が壊れている可能性があるなら直す
    if (!S.cache_valid)
      (void)S.eval_cost_full();

    // 木を戻す： new_par から u を外して old_par に戻す
    int cur_par = S.parent[mv.u]; // = mv.new_par のはず
    int idx = S.index_in_children(cur_par, mv.u);
    if (idx >= 0)
      S.erase_child(cur_par, idx);

    S.insert_child(mv.old_par, mv.old_idx, mv.u);
    S.parent[mv.u] = mv.old_par;

    // seq/visit_pts/K_move を “元の位置へ” fast splice で戻す
    // old_before_v は「元の u の直後に来ていた子」。それが -1 なら末尾。
    bool ok = S.apply_repar_fast_beforev(mv.u, mv.old_par, mv.old_before_v);
    if (!ok) {
      // 万一の保険（基本起きない想定）
      (void)S.eval_cost_full();
    }
  };

  while (true) {
    double t = timer.sec();
    if (t >= TIME_LIMIT)
      break;
    double T = temperature(t);

    Move mv;
    mv.type = sample_move_type();

    if (mv.type == FLIP) {
      if (!st.cache_valid)
        cur = st.eval_cost_full();
      mv.u = rng.next_int(0, st.M - 1);

      long long before_cost = st.cost;
      st.apply_flip_delta(mv.u);
      long long nxt = st.cost;
      long long delta = nxt - before_cost;

      bool accept = false;
      if (delta <= 0)
        accept = true;
      else {
        if (delta > (long long)(50.0 * T))
          accept = false;
        else
          accept = (rng.next_double01() < acceptance_prob(delta, T));
      }

      if (accept) {
        cur = nxt;
        if (cur < best_cost) {
          best_cost = cur;
          best = st;
        }
      } else {
        st.apply_flip_delta(mv.u);
        cur = st.cost;
      }
    } else {
      // structural (SWAP_SIB / REPAR)
      bool ok = apply_move_structural(st, mv);
      if (!ok)
        continue;

      // ここで st.cost が最新のはず：
      // - SWAP_SIB なら cache_valid=false なので full eval が必要
      // - REPAR なら apply_repar_fast_beforev が cost 更新済みで
      // cache_valid=true

      long long before_cost = cur;

      long long nxt;
      if (!st.cache_valid) {
        nxt = st.eval_cost_full(); // SWAP_SIB用
      } else {
        nxt = st.cost; // REPAR fast用
      }

      long long delta = nxt - before_cost;

      bool accept = false;
      if (delta <= 0)
        accept = true;
      else {
        if (delta > (long long)(50.0 * T))
          accept = false;
        else
          accept = (rng.next_double01() < acceptance_prob(delta, T));
      }

      if (accept) {
        cur = nxt;
        if (cur < best_cost) {
          best_cost = cur;
          best = st;
        }
      } else {
        undo_move(st, mv);
        // undo で cache_valid が true なら cost は更新済み
        if (!st.cache_valid)
          cur = st.eval_cost_full();
        else
          cur = st.cost;
      }
    }
  }

  best.eval_cost_full();

  // Postprocess with mid Z/X insertions
  PostPlan plan = postprocess_relocate_no_detour(best, a);

  // Output
  string ops = build_ops_with_insertions(plan.visit_pts, plan.mid_actions);
  for (char c : ops)
    cout << c << "\n";
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In member function 'bool State::apply_repar_fast(int, int, int, int, int)':
./Main.cpp:281:15: warning: unused variable 'segLen' [-Wunused-variable]
  281 |     const int segLen = r - l + 1;
      |               ^~~~~~
./Main.cpp:262:36: warning: unused parameter 'old_par' [-Wunused-parameter]
  262 |   bool apply_repar_fast(int u, int old_par, int old_idx, int new_par,
      |                                ~~~~^~~~~~~
./Main.cpp:262:49: warning: unused parameter 'old_idx' [-Wunused-parameter]
  262 |   bool apply_repar_fast(int u, int old_par, int old_idx, int new_par,
      |                                             ~~~~^~~~~~~

Judge Result