結果

問題 No.3735 Offbeat Permutation Tree
コンテスト
ユーザー Tehom
提出日時 2026-11-12 20:28:20
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 398 ms / 2,000 ms
+ 360µs
コード長 3,005 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,046 ms
コンパイル使用メモリ 392,224 KB
実行使用メモリ 333,220 KB
最終ジャッジ日時 2026-11-12 20:28:37
合計ジャッジ時間 16,413 ms
ジャッジサーバーID
(参考情報)
judge4_0 / judge1_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define ll long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define repl(i,a,b) for(ll i=(a);i<(b);i++)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()

template <typename T> bool chmin(T &a,T b){if(a>b){a=b;return true;} return false;}
template <typename T> bool chmax(T &a,T b){if(a<b){a=b;return true;} return false;}

/*

n偶数ならn=4のやつの周り2ずつ追加すれば良い

奇数は?
n=3は無理
n=5は
o-#-#-#-#
        |
#-#-#-o #
|       |
#-#-o #-#
|     |  
# o-#-#-#
|     | |
#-#-#-# o
あとはこれの周りに2ずつ追加すれば良い
*/ 

void solve(){
  int n; cin >> n;
  if(n<=3){
    cout << "-1\n";
    return;
  }

  vector<vector<pair<int,int>>> a(n+1);
  {
    a[4].push_back({1,2});
    a[4].push_back({3,4});
    a[4].push_back({1,5});
    a[4].push_back({2,6});
    a[4].push_back({4,8});
    a[4].push_back({6,7});
    a[4].push_back({7,8});
    a[4].push_back({7,11});
    a[4].push_back({9,10});
    a[4].push_back({11,12});
    a[4].push_back({9,13});
    a[4].push_back({11,15});
    a[4].push_back({12,16});
    a[4].push_back({13,14});
    a[4].push_back({14,15});
  }
  if(n == 4){
    for(auto [u,v]:a[4]){
      cout << u << " " << v << "\n";
    }
    return;
  }
  {
    a[5].push_back({1,2});
    a[5].push_back({2,3});
    a[5].push_back({3,4});
    a[5].push_back({4,5});
    a[5].push_back({5,10});
    a[5].push_back({6,7});
    a[5].push_back({7,8});
    a[5].push_back({8,9});
    a[5].push_back({6,11});
    a[5].push_back({10,15});
    a[5].push_back({11,12});
    a[5].push_back({12,13});
    a[5].push_back({14,15});
    a[5].push_back({11,16});
    a[5].push_back({14,19});
    a[5].push_back({17,18});
    a[5].push_back({18,19});
    a[5].push_back({19,20});
    a[5].push_back({16,21});
    a[5].push_back({19,24});
    a[5].push_back({20,25});
    a[5].push_back({21,22});
    a[5].push_back({22,23});
    a[5].push_back({23,24});
  }

  rep(i,6,n+1){
    a.push_back({});
    for(auto [u,v]:a[i-2]) a[i].push_back({u+i+(u-1)/(i-2)*2+1,v+i+(v-1)/(i-2)*2+1});

    if(i%4<=1){
      a[i].push_back({i+1,i+2});
      rep(j,0,i-2) a[i].push_back({i+1+i*j,i+1+(j+1)*i});
      rep(j,1,i) a[i].push_back({i*(i-1)+j,i*(i-1)+j+1});
      a[i].push_back({i*i-i-1,i*i-i});
      rep(j,1,i-1) a[i].push_back({i*j,i*(j+1)});
      rep(j,1,i) a[i].push_back({j,j+1});
    }
    else{
      a[i].push_back({i*i-2*i+1,i*i-2*i+2});
      rep(j,0,i-2) a[i].push_back({1+i*j,1+(j+1)*i});
      rep(j,1,i) a[i].push_back({j,j+1});
      a[i].push_back({2*i-1,2*i});
      rep(j,0,i-2) a[i].push_back({2*i+i*j,2*i+i*(j+1)});
      rep(j,1,i) a[i].push_back({i*i-i+j,i*i-i+j+1});
    }
  }
  assert(a[n].size() == n*n-1);
  for(auto [u,v]:a[n]){
    cout << u << " " << v << "\n";
  }

  return;
}

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


  int T=1;
  // cin >> T;
  rep(_,0,T){
    solve();
  }
}
0