#1170684 (C++23(gcc16)) No.3732 Labyrinth Maker

• 問題: No.3732 Labyrinth Maker
• ユーザー: 👑 kencho
• 提出日時: 2026-07-10 03:16:35
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 10,720 bytes
• コンパイル時間: 4,894 ms
• コンパイル使用メモリ: 369,148 KB
• 実行使用メモリ: 6,528 KB
• 最終ジャッジ日時: 2026-09-19 12:32:45
• 合計ジャッジ時間: 18,302 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 1
other	AC * 2 TLE * 1 -- * 56

ソースコード

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

struct XorShift {
  unsigned long long x;
  explicit XorShift(unsigned long long seed) : x(seed) {}
  unsigned int next() {
    x ^= x << 7;
    x ^= x >> 9;
    return (unsigned int)x;
  }
};

int N, M;
vector<int> A;
vector<int> answer;

bool solvePath(const vector<int> &order) {
  vector<int> label(M, 0);
  int currentLabel = 1;
  int sum = 0;

  for (int idx = 0; idx < M; idx++) {
    int v = order[idx];
    label[v] = currentLabel;
    sum += A[v];
    sum %= N;

    int remainingCells = M - idx - 1;
    int remainingGroups = N - currentLabel;
    if (currentLabel < N && sum == 0 && remainingCells >= remainingGroups) {
      currentLabel++;
      sum = 0;
    }
  }

  if (currentLabel == N && sum == 0) {
    answer.swap(label);
    return true;
  }
  return false;
}

bool trySnake(bool horizontal, bool reverseMajor, bool startForward) {
  vector<int> order;
  order.reserve(M);

  for (int k = 0; k < N; k++) {
    int major = reverseMajor ? N - 1 - k : k;
    bool forward = (k % 2 == 0 ? startForward : !startForward);

    for (int t = 0; t < N; t++) {
      int minor = forward ? t : N - 1 - t;
      int r = horizontal ? major : minor;
      int c = horizontal ? minor : major;
      order.push_back(r * N + c);
    }
  }

  return solvePath(order);
}

pair<int, int> originalCell(int r, int c, int mode) {
  switch (mode) {
    case 0: return {r, c};
    case 1: return {r, N - 1 - c};
    case 2: return {N - 1 - r, c};
    case 3: return {N - 1 - r, N - 1 - c};
    case 4: return {c, r};
    case 5: return {c, N - 1 - r};
    case 6: return {N - 1 - c, r};
    default: return {N - 1 - c, N - 1 - r};
  }
}

bool solveTree(const vector<int> &parent, const vector<int> &order) {
  vector<int> sum = A;
  vector<unsigned char> cut(M, 0);
  int root = order[0];
  int componentCount = 1;

  for (int idx = M - 1; idx >= 0; idx--) {
    int v = order[idx];
    if (v == root) continue;
    if (sum[v] == 0) {
      cut[v] = 1;
      componentCount++;
    } else {
      int p = parent[v];
      sum[p] += sum[v];
      sum[p] %= N;
    }
  }

  if (componentCount < N) return false;

  vector<int> component(M, -1);
  vector<int> componentParent;
  componentParent.reserve(componentCount);
  component[root] = 0;
  componentParent.push_back(-1);

  int created = 1;
  for (int idx = 1; idx < M; idx++) {
    int v = order[idx];
    int p = parent[v];
    if (cut[v]) {
      component[v] = created++;
      componentParent.push_back(component[p]);
    } else {
      component[v] = component[p];
    }
  }

  vector<int> childCount(componentCount, 0);
  for (int c = 1; c < componentCount; c++) childCount[componentParent[c]]++;

  queue<int> leaves;
  for (int c = 1; c < componentCount; c++) {
    if (childCount[c] == 0) leaves.push(c);
  }

  vector<unsigned char> removed(componentCount, 0);
  vector<int> finalLabel(componentCount, N);
  int nextLabel = 1;
  while (nextLabel < N) {
    if (leaves.empty()) return false;
    int c = leaves.front();
    leaves.pop();
    if (removed[c] || childCount[c] != 0) continue;

    removed[c] = 1;
    finalLabel[c] = nextLabel++;
    int p = componentParent[c];
    if (p >= 0) {
      childCount[p]--;
      if (p != 0 && !removed[p] && childCount[p] == 0) leaves.push(p);
    }
  }

  answer.assign(M, 0);
  for (int v = 0; v < M; v++) answer[v] = finalLabel[component[v]];
  return true;
}

bool tryCombTree(int mode) {
  vector<int> parent(M, -2), order;
  order.reserve(M);

  for (int r = 0; r < N; r++) {
    for (int c = 0; c < N; c++) {
      auto [origr, origc] = originalCell(r, c, mode);
      int v = origr * N + origc;
      order.push_back(v);

      if (r == 0 && c == 0) {
        parent[v] = -1;
      } else if (c == 0) {
        auto [pr, pc] = originalCell(r - 1, c, mode);
        parent[v] = pr * N + pc;
      } else {
        auto [pr, pc] = originalCell(r, c - 1, mode);
        parent[v] = pr * N + pc;
      }
    }
  }

  return solveTree(parent, order);
}

bool tryBackboneTree(int line, bool transpose, bool reverseMajor) {
  vector<int> parent(M, -2), order;
  order.reserve(M);

  auto idCell = [&](int r, int c) {
    if (reverseMajor) r = N - 1 - r;
    if (transpose) swap(r, c);
    return r * N + c;
  };

  auto addVertex = [&](int v, int p) {
    parent[v] = p;
    order.push_back(v);
  };

  addVertex(idCell(0, line), -1);
  for (int r = 0; r < N; r++) {
    if (r > 0) addVertex(idCell(r, line), idCell(r - 1, line));

    int prev = idCell(r, line);
    for (int c = line + 1; c < N; c++) {
      int v = idCell(r, c);
      addVertex(v, prev);
      prev = v;
    }

    prev = idCell(r, line);
    for (int c = line - 1; c >= 0; c--) {
      int v = idCell(r, c);
      addVertex(v, prev);
      prev = v;
    }
  }

  return solveTree(parent, order);
}

bool tryRandomDfs(unsigned long long seed) {
  XorShift rng(seed);
  vector<int> parent(M, -2), order, st;
  order.reserve(M);
  st.reserve(M);

  int root = (int)(rng.next() % M);
  parent[root] = -1;
  order.push_back(root);
  st.push_back(root);

  const int dr[4] = {1, -1, 0, 0};
  const int dc[4] = {0, 0, 1, -1};

  while (!st.empty()) {
    int v = st.back();
    int r = v / N;
    int c = v % N;
    int cand[4];
    int cnt = 0;

    for (int dir = 0; dir < 4; dir++) {
      int nr = r + dr[dir];
      int nc = c + dc[dir];
      if (nr < 0 || N <= nr || nc < 0 || N <= nc) continue;
      int to = nr * N + nc;
      if (parent[to] == -2) cand[cnt++] = to;
    }

    if (cnt == 0) {
      st.pop_back();
      continue;
    }

    int to = cand[rng.next() % cnt];
    parent[to] = v;
    order.push_back(to);
    st.push_back(to);
  }

  return solveTree(parent, order);
}

bool tryRandomBfs(unsigned long long seed) {
  XorShift rng(seed);
  vector<int> parent(M, -2), order;
  order.reserve(M);

  int root = (int)(rng.next() % M);
  parent[root] = -1;
  order.push_back(root);

  const int dr[4] = {1, -1, 0, 0};
  const int dc[4] = {0, 0, 1, -1};

  for (int head = 0; head < (int)order.size(); head++) {
    int v = order[head];
    int r = v / N;
    int c = v % N;
    int dirs[4] = {0, 1, 2, 3};
    for (int i = 3; i >= 1; i--) swap(dirs[i], dirs[rng.next() % (i + 1)]);

    for (int idx = 0; idx < 4; idx++) {
      int dir = dirs[idx];
      int nr = r + dr[dir];
      int nc = c + dc[dir];
      if (nr < 0 || N <= nr || nc < 0 || N <= nc) continue;
      int to = nr * N + nc;
      if (parent[to] != -2) continue;
      parent[to] = v;
      order.push_back(to);
    }
  }

  return solveTree(parent, order);
}

bool connectedMask(int mask) {
  int first = __builtin_ctz(mask);
  int seen = 0;
  queue<int> q;
  q.push(first);
  seen |= 1 << first;

  const int dr[4] = {1, -1, 0, 0};
  const int dc[4] = {0, 0, 1, -1};

  while (!q.empty()) {
    int v = q.front();
    q.pop();
    int r = v / N;
    int c = v % N;
    for (int dir = 0; dir < 4; dir++) {
      int nr = r + dr[dir];
      int nc = c + dc[dir];
      if (nr < 0 || N <= nr || nc < 0 || N <= nc) continue;
      int to = nr * N + nc;
      if ((mask >> to & 1) && !(seen >> to & 1)) {
        seen |= 1 << to;
        q.push(to);
      }
    }
  }

  return seen == mask;
}

bool solveExactSmall() {
  if (N > 4) return false;

  int full = (1 << M) - 1;
  vector<vector<int>> candidates(M);
  for (int mask = 1; mask <= full; mask++) {
    int sum = 0;
    for (int v = 0; v < M; v++) {
      if (mask >> v & 1) sum = (sum + A[v]) % N;
    }
    if (sum != 0 || !connectedMask(mask)) continue;
    int first = __builtin_ctz(mask);
    candidates[first].push_back(mask);
  }
  for (auto &v : candidates) {
    sort(v.begin(), v.end(), [](int x, int y) {
      return __builtin_popcount((unsigned)x) < __builtin_popcount((unsigned)y);
    });
  }

  vector<int> chosen;
  unordered_set<long long> bad;

  function<bool(int, int)> dfs = [&](int rest, int groupsLeft) -> bool {
    if (groupsLeft == 0) return rest == 0;
    if (__builtin_popcount((unsigned)rest) < groupsLeft) return false;

    long long key = ((long long)rest << 3) | groupsLeft;
    if (bad.count(key)) return false;

    int first = __builtin_ctz(rest);
    for (int mask : candidates[first]) {
      if ((mask & rest) != mask) continue;
      chosen.push_back(mask);
      if (dfs(rest ^ mask, groupsLeft - 1)) return true;
      chosen.pop_back();
    }

    bad.insert(key);
    return false;
  };

  if (!dfs(full, N)) return false;

  answer.assign(M, 0);
  for (int id = 0; id < (int)chosen.size(); id++) {
    int mask = chosen[id];
    for (int v = 0; v < M; v++) {
      if (mask >> v & 1) answer[v] = id + 1;
    }
  }
  return true;
}

void solveCase() {
  cin >> N;
  M = N * N;
  A.resize(M);

  int total = 0;
  for (int i = 0; i < M; i++) {
    int x;
    cin >> x;
    A[i] = x % N;
    total += A[i];
    total %= N;
  }

  if (total != 0) {
    cout << "-1\n";
    return;
  }

  if (solveExactSmall()) {
    // done
  } else {
    bool ok = false;
    for (int horizontal = 0; horizontal < 2 && !ok; horizontal++) {
      for (int reverseMajor = 0; reverseMajor < 2 && !ok; reverseMajor++) {
        for (int startForward = 0; startForward < 2 && !ok; startForward++) {
          ok = trySnake(horizontal, reverseMajor, startForward);
        }
      }
    }

    for (int mode = 0; mode < 8 && !ok; mode++) ok = tryCombTree(mode);

    vector<int> backboneLines;
    if (N <= 50) {
      for (int line = 0; line < N; line++) backboneLines.push_back(line);
    } else {
      int cand[] = {0, N - 1, N / 2, (N - 1) / 2, N / 3, (2 * N) / 3};
      for (int line : cand) {
        if (0 <= line && line < N) backboneLines.push_back(line);
      }
      sort(backboneLines.begin(), backboneLines.end());
      backboneLines.erase(unique(backboneLines.begin(), backboneLines.end()), backboneLines.end());
    }
    for (int line : backboneLines) {
      for (int transpose = 0; transpose < 2 && !ok; transpose++) {
        for (int reverseMajor = 0; reverseMajor < 2 && !ok; reverseMajor++) {
          ok = tryBackboneTree(line, transpose, reverseMajor);
        }
      }
      if (ok) break;
    }

    int attempts = 4;
    for (int t = 0; t < attempts && !ok; t++) {
      ok = tryRandomDfs(0x9e3779b97f4a7c15ULL + 1000003ULL * t + N);
    }
    for (int t = 0; t < attempts && !ok; t++) {
      ok = tryRandomBfs(0xbf58476d1ce4e5b9ULL + 1000033ULL * t + N);
    }

    if (!ok) {
      cout << "-1\n";
      return;
    }
  }

  for (int r = 0; r < N; r++) {
    for (int c = 0; c < N; c++) {
      if (c) cout << ' ';
      cout << answer[r * N + c];
    }
    cout << '\n';
  }
}

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

  int T;
  cin >> T;
  while (T--) solveCase();
  return 0;
}