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

• 問題: No.3735 Offbeat Permutation Tree
• ユーザー: tnakao0123
• 提出日時: 2026-09-30 12:13:22
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 3,116 bytes
• コンパイル時間: 399 ms
• コンパイル使用メモリ: 85,836 KB
• 実行使用メモリ: 22,236 KB
• 最終ジャッジ日時: 2026-09-30 12:13:29
• 合計ジャッジ時間: 7,166 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 2
other	AC * 3 WA * 32

ソースコード

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

#include<cstdio>
#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>;

/* 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));
}
  

/* 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);
  }
  
  return 0;
}