#1190804 (C++17) No.3735 Offbeat Permutation Tree

• 問題: No.3735 Offbeat Permutation Tree
• ユーザー: tnakao0123
• 提出日時: 2026-09-30 13:04:43
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 96 ms / 2,000 ms
• コード長: 4,605 bytes
• コンパイル時間: 490 ms
• コンパイル使用メモリ: 90,248 KB
• 実行使用メモリ: 21,988 KB
• 最終ジャッジ日時: 2026-09-30 13:04:51
• 合計ジャッジ時間: 5,848 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge4_0

ファイルパターン	結果
sample	AC * 2
other	AC * 35

ソースコード

/* -*- coding: utf-8 -*-
 *
 * 3735.cc:  No.3735 Offbeat Permutation Tree - yukicoder
 */

#include<cstdio>
#include<cassert>
#include<vector>
#include<map>
#include<algorithm>
#include<utility>
#include<tuple>

using namespace std;

/* constant */

const int MAX_N = 500;
const int MAX_NN = MAX_N * MAX_N;

/* typedef */

using pii = pair<int,int>;
using mpii = map<pii,int>;
using tp3 = tuple<int,int,int>;
using vtp3 = vector<tp3>;

struct UFT {
  vector<int> links, ranks, sizes;
  UFT() {}

  void init(int n) {
    links.resize(n);
    for (int i = 0; i < n; i++) links[i] = i;
    ranks.assign(n, 1);
    sizes.assign(n, 1);
  }

  int root(int i) {
    int i0 = i;
    while (links[i0] != i0) i0 = links[i0];
    return (links[i] = i0);
  }

  int rank(int i) { return ranks[root(i)]; }
  int size(int i) { return sizes[root(i)]; }
  bool same(int i, int j) { return root(i) == root(j); }

  int merge(int i0, int i1) {
    int r0 = root(i0), r1 = root(i1), mr;
    if (r0 == r1) return r0;
    if (ranks[r0] == ranks[r1]) {
      links[r1] = r0;
      sizes[r0] += sizes[r1];
      ranks[r0]++;
      mr = r0;
    }
    else if (ranks[r0] > ranks[r1]) {
      links[r1] = r0;
      sizes[r0] += sizes[r1];
      mr = r0;
    }
    else {
      links[r0] = r1;
      sizes[r1] += sizes[r0];
      mr = r1;
    }
    return mr;
  }
};

/* global variables */

/*
  n=4:
  +-o +-+
  |   | |
  +-+-+ o
      |
  o +-+-+
  | |   |
  +-+ o-+
 */
const tp3 gn4[15] = {
  {0, 0, 0}, {0, 2, 0}, {1, 0, 0}, {1, 1, 0},
  {2, 1, 0}, {2, 2, 0}, {3, 0, 0}, {3, 2, 0},
  {0, 0, 1}, {0, 2, 1}, {0, 3, 1}, {1, 2, 1},
  {2, 0, 1}, {2, 1, 1}, {2, 3, 1},
};

/*
  n=5:
  +-+-+-+-o
  |
  +-o +-+-+
  |   |   |
  +-+-+ o-+
      |
  o +-+-+-+
  | |     |
  +-+ o-+-+
 */
const tp3 gn5[24] = {
  {0, 0, 0}, {0, 1, 0}, {0, 2, 0}, {0, 3, 0},
  {1, 0, 0}, {1, 2, 0}, {1, 3, 0},
  {2, 0, 0}, {2, 1, 0}, {2, 3, 0},
  {3, 1, 0}, {3, 2, 0}, {3, 3, 0},
  {4, 0, 0}, {4, 2, 0}, {4, 3, 0},
  {0, 0, 1},
  {1, 0, 1}, {1, 2, 1}, {1, 4, 1},
  {2, 2, 1},
  {3, 0, 1}, {3, 1, 1}, {3, 4, 1},
};

/* subroutines */

void addedge(vtp3 &es, mpii &dgs, const int uy, const int ux, const int di) {
  es.push_back({uy, ux, di});
  int vy = uy + di, vx = ux + (di ^ 1);
  dgs[{uy, ux}]++;
  dgs[{vy, vx}]++;
}
void addedge(vtp3 &es, mpii &dgs, const tp3 &e) {
  addedge(es, dgs, get<0>(e), get<1>(e), get<2>(e));
}

bool check(int n, vtp3 &es, mpii &dgs, int miny) {
  bool hcs[MAX_N] = {}, vcs[MAX_N] = {};
  for (auto &[p, d]: dgs)
    if (d == 1) {
      auto [y, x] = p;
      y -= miny;
      if (hcs[y] || vcs[x]) return false;
      hcs[y] = vcs[x] = true;
    }

  int nn = n * n;
  UFT uft;
  uft.init(nn);

  for (auto [uy, ux, di]: es) {
    uy -= miny;
    int u = uy * n + ux;
    int vy = uy + di, vx = ux + (di ^ 1), v = vy * n + vx;
    if (uft.same(u, v)) return false;
    uft.merge(u, v);
  }

  return (uft.size(0) == nn);
}

/* main */

int main() {
  int n;
  scanf("%d", &n);
  if (n <= 3) { puts("-1"); return 0; }

  int m = 4 + (n & 1);
  int gen = m * m - 1;
  const auto &gn = (m == 4) ? gn4 : gn5;

  vtp3 es;
  mpii dgs;
  for (int i = 0; i < gen; i++) addedge(es, dgs, gn[i]);

  int miny = 0, maxy = m - 1;
  while (m < n) {
    if (dgs[{maxy, m - 1}] > 1) { // expand to right-down
      addedge(es, dgs, maxy + 1, m, 1);
      for (int x = m - 1; x >= 0; x--) addedge(es, dgs, maxy + 2, x, 0);
      addedge(es, dgs, maxy + 1, 0, 1);
      for (int x = 0; x < m - 1; x++) addedge(es, dgs, maxy + 1, x, 0);
      addedge(es, dgs, maxy, m - 1, 1);
      for (int y = maxy + 1; y >= miny; y--) addedge(es, dgs, y, m + 1, 1);
      addedge(es, dgs, miny, m, 0);
      for (int y = miny; y < maxy; y++) addedge(es, dgs, y, m, 1);
      addedge(es, dgs, maxy, m - 1, 0);
      maxy += 2;
    }
    else { // expand to right-up
      addedge(es, dgs, miny - 2, m, 1);
      for (int x = m - 1; x >= 0; x--) addedge(es, dgs, miny - 2, x, 0);
      addedge(es, dgs, miny - 2, 0, 1);
      for (int x = 0; x < m - 1; x++) addedge(es, dgs, miny - 1, x, 0);
      addedge(es, dgs, miny - 1, m - 1, 1);
      for (int y = miny - 2; y < maxy; y++) addedge(es, dgs, y, m + 1, 1);
      addedge(es, dgs, maxy, m, 0);
      for (int y = maxy - 1; y >= miny; y--) addedge(es, dgs, y, m, 1);
      addedge(es, dgs, miny, m - 1, 0);
      miny -= 2;
    }
    m += 2;
  }

  for (auto [uy, ux, di]: es) {
    uy -= miny;
    int u = uy * n + ux;
    int vy = uy + di, vx = ux + (di ^ 1), v = vy * n + vx;
    if (u > v) swap(u, v);
    printf("%d %d\n", u + 1, v + 1);
  }

  //assert(check(n, es, dgs, miny));
  
  return 0;
}