結果
| 問題 | No.3735 Offbeat Permutation Tree |
| コンテスト | |
| ユーザー |
Tehom
|
| 提出日時 | 2026-11-12 20:28:20 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 398 ms / 2,000 ms |
| + 360µs | |
| コード長 | 3,005 bytes |
| 記録 | |
| コンパイル時間 | 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 |
ソースコード
#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();
}
}
Tehom