結果

問題 No.3735 Offbeat Permutation Tree
コンテスト
ユーザー mono
提出日時 2026-09-19 18:20:30
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,651 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,808 ms
コンパイル使用メモリ 388,924 KB
実行使用メモリ 12,784 KB
最終ジャッジ日時 2026-09-19 18:20:43
合計ジャッジ時間 10,651 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge5_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 2 WA * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#pragma GCC optimize ("O3,inline,omit-frame-pointer,no-asynchronous-unwind-tables,fast-math")
#include <bits/stdc++.h>
#include <unordered_map>
#include <stdlib.h>
using namespace std;
#define rep(i, a, n) for(ll i = a; i < n; i++)
#define rrep(i, a, n) for(ll i = a; i >= n; i--)
#define inr(l, x, r) (l <= x && x < r)
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) (x).begin(), (x).end()
//constexpr ll MOD = 1000000007;
constexpr ll MOD = 998244353;
constexpr int IINF = 1001001001;
constexpr ll INF = 1LL<<60;
template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    ll n; cin >> n;
    if(n <= 3){
        cout << -1 << endl;
        return 0;
    }
    vector<pll> edges;
    ll now;
    auto plus = [&]() -> void {
        now += 2;
        for(auto& p: edges){
            ll x = (p.first-1)/(now-2), y = (p.first-1)%(now-2);
            ll xx = (p.second-1)/(now-2), yy = (p.second-1)%(now-2);
            x++;y++;xx++;yy++;
            p = {y*now+now-x,yy*now+now-xx};
        }
        edges.emplace_back(now*(now-2)+1,now*(now-2)+2);
        edges.emplace_back(now*2,now*2-1);
        rep(i,0,now-1){
            edges.emplace_back(i+1,i+2);
            edges.emplace_back(now*(n-1)+i+1,now*(n-1)+i+2);
        }
        rep(i,0,now-2){
            edges.emplace_back(now*i+1,now*(i+1)+1);
            edges.emplace_back(now*(i+2)+now,now*(i+1)+now);
        }
    };
    if(n%2 == 0){
        now  = 4;
        edges = {
            {1, 2},
            {3 ,4},
            {1 ,5},
            {2 ,6},
            {4 ,8},
            {6 ,7},
            {7 ,8},
            {7 ,11},
            {9 ,10},
            {11, 12},
            {9 ,13},
            {11, 15},
            {12, 16},
            {13, 14},
            {14, 15}
        };
        rep(i,0,(n-4)/2) plus();
    }else{
        now = 5;
        edges = {
            {1,2},
            {2,3},
            {4,5},
            {1,6},
            {3,8},
            {5,10},
            {6,7},
            {8,9},
            {9,14},
            {10,15},
            {12,13},
            {13,14},
            {14,15},
            {11,16},
            {12,17},
            {14,19},
            {15,20},
            {16,21},
            {17,22},
            {18,23},
            {19,24},
            {20,25},
            {21,22},
            {23,24}
        };
        rep(i,0,(n-4)/2) plus();
    }

    for(auto [x,y] : edges) cout << x << " " << y << endl;
    return 0;
}
0