結果
| 問題 | No.1061 素敵な数列 |
| ユーザー |
 ecottea
|
| 提出日時 | 2025-06-11 17:30:53 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 23 ms / 2,000 ms |
| コード長 | 19,490 bytes |
| コンパイル時間 | 6,060 ms |
| コンパイル使用メモリ | 270,760 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-06-11 17:31:04 |
| 合計ジャッジ時間 | 9,413 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 33 |
ソースコード
#ifndef HIDDEN_IN_VS // 折りたたみ用
// 警告の抑制
#define _CRT_SECURE_NO_WARNINGS
// ライブラリの読み込み
#include <bits/stdc++.h>
using namespace std;
// 型名の短縮
using ll = long long; using ull = unsigned long long; // -2^63 ～ 2^63 = 9e18（int は -2^31 ～ 2^31 = 2e9）
using pii = pair<int, int>; using pll = pair<ll, ll>; using pil = pair<int, ll>; using pli = pair<ll, int>;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vvvvi = vector<vvvi>;
using vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>; using vvvvl = vector<vvvl>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vc = vector<char>; using vvc = vector<vc>; using vvvc = vector<vvc>;
using vd = vector<double>; using vvd = vector<vd>; using vvvd = vector<vvd>;
template <class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
using Graph = vvi;
// 定数の定義
const double PI = acos(-1);
int DX[4] = { 1, 0, -1, 0 }; // 4 近傍（下，右，上，左）
int DY[4] = { 0, 1, 0, -1 };
int INF = 1001001001; ll INFL = 4004004003094073385LL; // (int)INFL = INF, (int)(-INFL) = -INF;
// 入出力高速化
struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp;
// 汎用マクロの定義
#define all(a) (a).begin(), (a).end()
#define sz(x) ((int)(x).size())
#define lbpos(a, x) (int)distance((a).begin(), std::lower_bound(all(a), (x)))
#define ubpos(a, x) (int)distance((a).begin(), std::upper_bound(all(a), (x)))
#define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");}
#define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順
#define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順
#define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s から t まで降順
#define repe(v, a) for(const auto& v : (a)) // a の全要素（変更不可能）
#define repea(v, a) for(auto& v : (a)) // a の全要素（変更可能）
#define repb(set, d) for(int set = 0, set##_ub = 1 << int(d); set < set##_ub; ++set) // d ビット全探索（昇順）
#define repis(i, set) for(int i = lsb(set), bset##i = set; i < 32; bset##i -= 1 << i, i = lsb(bset##i)) // set の全要素（昇順）
#define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て（昇順）
#define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去
#define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了
#define inQ(x, y, u, l, d, r) ((u) <= (x) && (l) <= (y) && (x) < (d) && (y) < (r)) // 半開矩形内判定
// 汎用関数の定義
template <class T> inline ll powi(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; }
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新（更新されたら true を返す）
template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新（更新されたら true を返す）
template <class T> inline T getb(T set, int i) { return (set >> i) & T(1); }
template <class T> inline T smod(T n, T m) { n %= m; if (n < 0) n += m; return n; } // 非負mod
// 演算子オーバーロード
template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template <class T> inline istream& operator>>(istream& is, vector<T>& v) { repea(x, v) is >> x; return is; }
template <class T> inline vector<T>& operator--(vector<T>& v) { repea(x, v) --x; return v; }
template <class T> inline vector<T>& operator++(vector<T>& v) { repea(x, v) ++x; return v; }
#endif // 折りたたみ用
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#ifdef _MSC_VER
#include "localACL.hpp"
#endif
using mint = modint998244353;
//using mint = static_modint<(int)1e9 + 7>;
//using mint = modint; // mint::set_mod(m);
namespace atcoder {
inline istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; }
inline ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; }
}
using vm = vector<mint>; using vvm = vector<vm>; using vvvm = vector<vvm>; using vvvvm = vector<vvvm>; using pim = pair<int, mint>;
#endif
#ifdef _MSC_VER // 手元環境（Visual Studio）
#include "local.hpp"
#else // 提出用（gcc）
inline int popcount(int n) { return __builtin_popcount(n); }
inline int popcount(ll n) { return __builtin_popcountll(n); }
inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : 32; }
inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : 64; }
inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; }
inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; }
#define dump(...)
#define dumpel(v)
#define dump_math(v)
#define input_from_file(f)
#define output_to_file(f)
#define Assert(b) { if (!(b)) { vc MLE(1<<30); EXIT(MLE.back()); } } // RE の代わりに MLE を出す
#endif
vi naive(int n) {
vector<vector<tuple<int, int, int>>> ps(n);
rep(i, 3 * n) repi(j, i + 1, 3 * n - 1) repi(k, j + 1, 3 * n - 1) {
int d = abs((j - i) - (k - j)); // |i - 2j + k|
if (d < n) ps[d].push_back({ i, j, k });
}
vi a(3 * n, -1);
vvi res;
function<void(int)> rf = [&](int d) {
if (d == n) {
res.push_back(a);
return;
}
repe(p, ps[d]) {
auto [i, j, k] = p;
if (a[i] != -1 || a[j] != -1 || a[k] != -1) continue;
a[i] = a[j] = a[k] = d;
rf(d + 1);
a[i] = a[j] = a[k] = -1;
}
};
rf(0);
//dumpel(res);
dump(res.back());
dump(sz(res));
return res.empty() ? vi() : res[0];
}
/*
1
0: 0 0 0
2
3
0: 0 0 0 1 2 1 1 2 2
1: 0 0 0 2 2 1 1 2 1
2: 0 1 0 2 0 1 2 2 1
3: 0 2 0 1 0 2 1 2 1
4: 0 2 0 2 0 1 1 2 1
5: 2 0 0 0 1 2 1 1 2
6: 2 0 0 0 2 1 2 1 1
7: 1 0 2 0 1 0 2 1 2
8: 1 0 2 1 0 1 2 0 2
9: 2 0 2 1 0 1 2 0 1
10: 2 1 2 0 1 0 2 0 1
11: 1 2 1 1 0 2 0 2 0
12: 1 2 1 2 0 1 0 2 0
13: 1 2 2 1 0 2 0 1 0
14: 1 1 2 1 2 0 0 0 2
15: 2 1 1 2 1 0 0 0 2
16: 1 2 1 1 2 2 0 0 0
17: 2 2 1 1 2 1 0 0 0
4
0: 0 0 0 1 1 3 1 2 2 3 3 2
1: 0 0 0 1 3 1 1 2 3 3 2 2
2: 0 0 0 1 3 1 2 2 1 3 2 3
3: 0 0 0 1 3 3 1 2 1 3 2 2
4: 0 0 0 1 3 2 1 2 3 3 1 2
5: 0 0 0 1 3 3 1 2 2 3 1 2
6: 0 0 0 1 3 2 3 1 2 2 1 3
7: 0 0 0 2 1 3 1 1 2 3 3 2
8: 0 0 0 3 1 2 1 1 3 2 3 2
9: 0 0 0 3 1 2 1 2 3 1 3 2
10: 0 0 0 3 1 3 1 2 2 1 3 2
...
369: 2 3 3 2 2 1 3 1 1 0 0 0
5
0: 0 0 0 1 1 2 1 3 4 4 2 3 3 2 4
1: 0 0 0 1 1 3 1 2 4 4 3 2 3 2 4
2: 0 0 0 1 1 4 1 4 2 3 3 2 2 4 3
3: 0 0 0 1 4 1 1 2 2 3 4 2 4 3 3
4: 0 0 0 1 3 1 1 4 2 3 2 3 4 4 2
5: 0 0 0 1 4 1 1 3 3 2 2 4 3 2 4
6: 0 0 0 1 3 1 1 4 3 3 2 2 4 4 2
7: 0 0 0 1 4 1 4 2 1 3 2 2 4 3 3
8: 0 0 0 1 4 1 4 2 1 3 3 2 4 2 3
9: 0 0 0 1 4 1 3 4 1 2 3 3 2 2 4
10: 0 0 0 1 3 1 4 4 1 3 2 3 4 2 2
...
4597: 3 4 2 2 3 3 2 4 1 4 1 1 0 0 0
6
0: 0 0 0 1 1 2 1 2 3 4 5 2 3 3 4 4 5 5
1: 0 0 0 1 1 2 1 2 4 5 3 2 3 4 4 5 5 3
2: 0 0 0 1 1 2 1 3 2 4 5 3 3 2 4 4 5 5
3: 0 0 0 1 1 2 1 5 2 5 3 4 4 2 3 3 5 4
4: 0 0 0 1 1 2 1 5 5 2 4 2 3 3 5 4 4 3
5: 0 0 0 1 1 2 1 3 4 2 5 3 3 4 4 2 5 5
6: 0 0 0 1 1 2 1 5 5 2 4 4 3 3 5 2 4 3
7: 0 0 0 1 1 2 1 3 5 5 2 4 3 2 3 5 4 4
8: 0 0 0 1 1 2 1 4 5 5 2 3 3 2 4 5 3 4
9: 0 0 0 1 1 2 1 5 5 4 2 3 3 2 5 4 3 4
10: 0 0 0 1 1 2 1 3 4 5 2 3 3 4 4 5 5 2
...
228267: 5 5 4 4 3 3 2 5 4 3 2 1 2 1 1 0 0 0
*/
vi naive2(int n) {
vector<vector<tuple<int, int, int>>> ps(n);
rep(i, 3 * n) repi(j, i + 1, 3 * n - 1) repi(k, j + 1, 3 * n - 1) {
int d = abs((j - i) - (k - j)); // |i - 2j + k|
if (d < n) ps[d].push_back({ i, j, k });
}
vi a(3 * n, -1);
function<bool(int)> rf = [&](int d) {
if (d == n) {
return true;
}
repe(p, ps[d]) {
auto [i, j, k] = p;
if (a[i] != -1 || a[j] != -1 || a[k] != -1) continue;
a[i] = a[j] = a[k] = d;
if (rf(d + 1)) return true;
a[i] = a[j] = a[k] = -1;
}
return false;
};
if (!rf(0)) return vi();
return a;
}
void zikken2() {
repi(n, 1, 20) {
dump(n, ":", naive2(n));
}
exit(0);
}
/*
1 : 0 0 0
2 :
3 : 0 0 0 1 2 1 1 2 2
4 : 0 0 0 1 1 3 1 2 2 3 3 2
5 : 0 0 0 1 1 2 1 3 4 4 2 3 3 2 4
6 : 0 0 0 1 1 2 1 2 3 4 5 2 3 3 4 4 5 5
7 : 0 0 0 1 1 2 1 2 3 5 6 2 3 3 4 5 5 6 6 4 4
8 : 0 0 0 1 1 2 1 2 3 3 7 2 4 3 6 6 5 5 4 7 4 7 6 5
9 : 0 0 0 1 1 2 1 2 3 3 4 2 7 3 4 8 5 5 6 6 7 7 4 5 8 8 6
10 : 0 0 0 1 1 2 1 2 3 3 4 2 4 3 5 7 9 8 4 8 6 6 5 7 7 5 9 9 6 8
11 : 0 0 0 1 1 2 1 2 3 3 4 2 4 3 5 5 9 6 4 10 7 5 8 8 6 6 9 9 7 7 10 10 8
12 : 0 0 0 1 1 2 1 2 3 3 4 2 4 3 5 5 6 11 4 6 10 5 9 9 8 8 7 7 6 11 11 10 10 9 8 7
13 : 0 0 0 1 1 2 1 2 3 3 4 2 4 3 5 5 6 6 4 10 11 5 12 7 6 7 9 9 8 8 10 10 11 11 7 12 12 9 8
14 : 0 0 0 1 1 2 1 2 3 3 4 2 4 3 5 5 6 6 4 7 11 5 13 10 6 12 8 7 7 8 9 9 11 11 10 10 13 13 12 12 8 9
15 : 0 0 0 1 1 2 1 2 3 3 4 2 4 3 5 5 6 6 4 7 7 5 8 10 6 13 14 9 7 12 12 11 11 8 10 10 8 9 9 13 13 14 14 12 11
16 : 0 0 0 1 1 2 1 2 3 3 4 2 4 3 5 5 6 6 4 7 7 5 8 15 6 8 14 9 7 10 13 10 12 12 11 11 8 9 9 15 15 14 14 10 13 13 12 11
17 : 0 0 0 1 1 2 1 2 3 3 4 2 4 3 5 5 6 6 4 7 7 5 8 8 6 9 14 10 7 16 12 13 8 15 15 11 11 9 10 10 9 14 14 12 12 13 13 16 11 16 15
18 : 0 0 0 1 1 2 1 2 3 3 4 2 4 3 5 5 6 6 4 7 7 5 8 8 6 9 9 15 7 17 10 16 8 11 14 14 9 13 13 12 12 10 10 15 15 11 11 17 17 16 14 16 13 12
*/
vi naive3(int n) {
vector<vector<tuple<int, int, int>>> ps(n);
rep(i, 3 * n) repi(j, i + 1, 3 * n - 1) repi(k, j + 1, 3 * n - 1) {
int d = abs((j - i) - (k - j)); // |i - 2j + k|
if ((j - i == 1 || k - j == 1) && d < n) ps[d].push_back({ i, j, k });
}
vi a(3 * n, -1);
function<bool(int)> rf = [&](int d) {
if (d == n) {
return true;
}
repe(p, ps[d]) {
auto [i, j, k] = p;
if (a[i] != -1 || a[j] != -1 || a[k] != -1) continue;
a[i] = a[j] = a[k] = d;
if (rf(d + 1)) return true;
a[i] = a[j] = a[k] = -1;
}
return false;
};
if (!rf(0)) return vi();
return a;
}
void zikken3() {
repi(n, 1, 20) {
dump(n, ":", naive3(n));
}
exit(0);
}
/*
1 : 0 0 0
2 :
3 : 0 0 0 1 2 1 1 2 2
4 : 0 0 0 1 1 3 1 2 2 3 3 2
5 : 0 0 0 1 3 1 1 4 3 3 2 2 4 4 2
6 : 0 0 0 1 1 4 1 3 3 5 4 4 3 2 2 5 5 2
7 : 0 0 0 1 1 3 1 6 6 3 3 5 2 2 4 6 2 5 5 4 4
8 : 0 0 0 1 1 2 1 3 2 2 6 3 3 5 7 4 4 6 6 5 5 4 7 7
9 : 0 0 0 1 1 2 1 3 2 2 4 3 3 7 8 4 4 6 6 5 5 7 7 8 8 6 5
10 : 0 0 0 1 1 2 1 3 2 2 4 3 3 9 6 4 4 8 5 5 7 6 6 9 9 5 8 8 7 7
11 : 0 0 0 1 1 2 1 3 2 2 4 3 3 10 10 4 4 5 7 9 6 6 8 5 5 10 7 7 6 9 9 8 8
12 : 0 0 0 1 1 2 1 3 2 2 4 3 3 5 5 4 4 6 9 10 5 11 8 8 6 6 7 7 9 9 10 10 8 11 11 7
13 : 0 0 0 1 1 2 1 3 2 2 4 3 3 5 5 4 4 6 6 11 5 7 10 12 12 6 8 9 9 7 7 11 11 10 10 8 8 12 9
14 : 0 0 0 1 1 2 1 3 2 2 4 3 3 5 5 4 4 6 6 7 5 9 10 11 12 6 13 7 7 8 8 9 9 10 10 11 11 12 12 8 13 13
15 : 0 0 0 1 1 2 1 3 2 2 4 3 3 5 5 4 4 6 6 7 5 13 8 9 14 6 10 7 7 11 12 8 8 9 9 13 13 10 10 14 14 11 11 12 12
16 : 0 0 0 1 1 2 1 3 2 2 4 3 3 5 5 4 4 6 6 7 5 8 8 14 11 6 13 7 7 12 15 8 10 10 9 9 11 11 14 14 13 13 12 12 10 9 15 15
17 : 0 0 0 1 1 2 1 3 2 2 4 3 3 5 5 4 4 6 6 7 5 8 8 9 16 6 12 7 7 13 14 8 15 9 9 10 10 11 11 12 12 16 16 13 13 14 14 10 15 15 11
18 : 0 0 0 1 1 2 1 3 2 2 4 3 3 5 5 4 4 6 6 7 5 8 8 9 9 6 16 7 7 15 10 8 17 13 9 12 12 14 14 11 11 10 10 16 16 15 15 13 13 12 17 17 11 14
19 : 0 0 0 1 1 2 1 3 2 2 4 3 3 5 5 4 4 6 6 7 5 8 8 9 9 6 10 7 7 17 14 8 18 15 9 16 16 10 10 13 13 12 12 11 11 14 14 17 17 15 15 18 18 16 13 12 11
20 : 0 0 0 1 1 2 1 3 2 2 4 3 3 5 5 4 4 6 6 7 5 8 8 9 9 6 10 7 7 11 16 8 18 15 9 17 19 10 10 14 14 11 11 13 13 12 12 16 16 15 15 18 18 17 17 14 19 19 13 12
*/
vi naive4(int l, int r) {
vector<vector<tuple<int, int, int>>> ps(r);
int n = r - l;
rep(i, 3 * n) repi(j, i + 1, 3 * n - 1) repi(k, j + 1, 3 * n - 1) {
int d = abs((j - i) - (k - j)); // |i - 2j + k|
if ((j - i == 1 || k - j == 1) && l <= d && d < r) ps[d].push_back({ i, j, k });
}
vi a(3 * n, -1);
function<bool(int)> rf = [&](int d) {
if (d == r) {
dump(a);
return false;
return true;
}
repe(p, ps[d]) {
auto [i, j, k] = p;
if (a[i] != -1 || a[j] != -1 || a[k] != -1) continue;
a[i] = a[j] = a[k] = d;
if (rf(d + 1)) return true;
a[i] = a[j] = a[k] = -1;
}
return false;
};
if (!rf(l)) return vi();
return a;
}
/*
4 8
7 4 6 6 5 5 4 4 7 7 6 5
5 6 7 7 4 4 5 5 6 6 4 7
5 10
8 5 9 6 6 7 7 5 5 8 8 6 9 9 7
8 5 9 9 6 7 7 5 5 8 8 6 6 9 7
7 9 6 6 8 8 5 5 7 7 6 9 9 5 8
7 9 9 6 8 8 5 5 7 7 6 6 9 5 8
6 12
10 11 6 6 9 9 8 8 7 7 6 10 10 11 11 9 8 7
9 11 11 10 10 6 8 8 7 7 9 9 6 6 11 10 8 7
7 8 10 11 6 6 9 9 7 7 8 8 6 10 10 11 11 9
7 8 9 11 11 10 10 6 7 7 8 8 9 9 6 6 11 10
7 14
7 12 9 13 10 10 11 11 7 7 8 8 9 9 12 12 10 13 13 11 8
7 12 9 13 13 10 11 11 7 7 8 8 9 9 12 12 10 10 13 11 8
13 10 7 7 12 9 9 11 11 8 8 7 10 10 13 13 9 12 12 8 11
13 10 7 7 12 12 9 11 11 8 8 7 10 10 13 13 9 9 12 8 11
13 10 7 12 12 9 9 11 8 8 7 7 10 10 13 13 9 12 8 11 11
13 10 7 12 12 9 9 11 11 8 7 7 10 10 13 13 9 12 8 8 11
8 13 10 7 11 11 12 9 9 8 8 7 7 10 10 13 13 11 9 12 12
8 13 10 7 11 11 12 12 9 8 8 7 7 10 10 13 13 11 9 9 12
12 13 13 7 9 9 10 11 11 8 8 7 7 12 12 9 13 10 10 8 11
13 10 10 7 12 9 9 11 11 8 8 7 7 10 13 13 9 12 12 8 11
13 13 10 7 12 9 9 11 11 8 8 7 7 10 10 13 9 12 12 8 11
13 10 10 7 12 12 9 11 11 8 8 7 7 10 13 13 9 9 12 8 11
13 13 10 7 12 12 9 11 11 8 8 7 7 10 10 13 9 9 12 8 11
13 9 12 12 7 7 10 11 11 8 8 9 9 7 13 13 12 10 10 8 11
13 8 8 12 7 11 11 10 10 9 9 8 7 7 13 13 12 12 11 10 9
10 13 9 9 12 7 7 11 11 8 8 10 10 9 7 13 13 12 12 8 11
9 13 8 8 12 7 11 11 10 10 9 9 8 7 7 13 13 12 12 11 10
10 12 12 13 13 7 9 11 11 8 8 10 10 7 7 12 9 9 13 8 11
11 8 13 9 9 12 7 7 10 10 8 8 11 11 9 7 13 13 12 12 10
10 11 12 12 13 13 7 7 8 9 9 10 10 11 11 7 12 8 8 13 9
11 8 12 12 13 13 7 9 10 10 8 8 11 11 7 7 12 9 9 13 10
9 10 11 12 12 13 13 7 7 8 9 9 10 10 11 11 7 12 8 8 13
11 8 10 10 12 13 13 7 9 9 8 8 11 11 10 7 7 12 12 9 13
11 8 12 9 9 13 10 10 7 7 8 8 11 11 9 12 12 7 10 13 13
11 8 12 9 9 13 13 10 7 7 8 8 11 11 9 12 12 7 10 10 13
11 8 12 12 9 13 10 10 7 7 8 8 11 11 9 9 12 7 10 13 13
11 8 12 12 9 13 13 10 7 7 8 8 11 11 9 9 12 7 10 10 13
11 8 10 10 13 9 12 12 7 7 8 8 11 11 10 9 9 7 13 13 12
12 9 9 11 13 13 10 10 7 7 8 8 9 12 12 11 11 7 10 13 8
12 12 9 11 13 13 10 10 7 7 8 8 9 9 12 11 11 7 10 13 8
11 8 8 12 9 13 13 10 10 7 7 8 11 11 9 9 12 12 7 10 13
11 11 8 12 9 13 13 10 10 7 7 8 8 11 9 9 12 12 7 10 13
11 8 12 9 9 13 13 10 10 7 8 8 11 11 9 12 12 7 7 10 13
11 8 12 12 9 13 13 10 10 7 8 8 11 11 9 9 12 7 7 10 13
8 11 13 10 10 12 12 9 9 8 8 7 7 11 11 10 13 13 9 12 7
8 11 13 13 10 12 12 9 9 8 8 7 7 11 11 10 10 13 9 12 7
*/
void zikken4() {
repi(r, 1, 10) rep(l, r) {
dump(l, r, ":", naive4(l, r));
}
exit(0);
}
/*
0 1 : 0 0 0
0 2 :
1 2 :
0 3 : 0 0 0 1 2 1 1 2 2
1 3 : 1 2 1 1 2 2
2 3 :
0 4 : 0 0 0 1 1 3 1 2 2 3 3 2
1 4 : 1 1 3 1 2 2 3 3 2
2 4 :
3 4 :
0 5 : 0 0 0 1 1 2 1 3 4 4 2 3 3 2 4
1 5 : 1 1 2 1 3 4 4 2 3 3 2 4
2 5 : 2 3 4 2 2 3 3 4 4
3 5 :
4 5 :
0 6 : 0 0 0 1 1 2 1 2 3 4 5 2 3 3 4 4 5 5
1 6 : 1 1 2 1 2 3 4 5 2 3 3 4 4 5 5
2 6 : 2 3 2 4 5 5 2 3 4 4 3 5
3 6 :
4 6 :
5 6 :
0 7 : 0 0 0 1 1 2 1 2 3 5 6 2 3 3 4 5 5 6 6 4 4
1 7 : 1 1 2 1 2 3 5 6 2 3 3 4 5 5 6 6 4 4
2 7 : 2 2 3 6 2 5 5 3 4 3 6 6 5 4 4
3 7 : 3 6 3 5 5 4 4 3 6 6 5 4
4 7 :
5 7 :
6 7 :
0 8 : 0 0 0 1 1 2 1 2 3 3 7 2 4 3 6 6 5 5 4 7 4 7 6 5
1 8 : 1 1 2 1 2 3 3 7 2 4 3 6 6 5 5 4 7 4 7 6 5
2 8 : 2 2 3 3 2 5 6 3 7 4 4 5 5 6 6 4 7 7
3 8 : 3 3 7 4 6 3 5 5 4 4 7 7 6 5 6
4 8 : 7 4 6 6 5 5 4 4 7 7 6 5
5 8 :
6 8 :
7 8 :
0 9 : 0 0 0 1 1 2 1 2 3 3 4 2 7 3 4 8 5 5 6 6 7 7 4 5 8 8 6
1 9 : 1 1 2 1 2 3 3 4 2 7 3 4 8 5 5 6 6 7 7 4 5 8 8 6
2 9 : 2 2 3 3 2 4 6 3 4 8 5 7 7 6 6 4 5 5 8 8 7
3 9 : 3 3 4 7 4 3 6 8 5 5 4 7 7 6 6 5 8 8
4 9 : 4 7 4 8 5 5 6 6 4 7 7 5 8 8 6
5 9 :
6 9 :
7 9 :
8 9 :
0 10 : 0 0 0 1 1 2 1 2 3 3 4 2 4 3 5 7 9 8 4 8 6 6 5 7 7 5 9 9 6 8
1 10 : 1 1 2 1 2 3 3 4 2 4 3 5 7 9 8 4 8 6 6 5 7 7 5 9 9 6 8
2 10 : 2 2 3 3 2 4 4 3 8 5 9 4 6 7 7 5 5 8 8 6 6 9 7 9
3 10 : 3 3 4 4 9 3 5 6 4 7 8 8 5 5 6 6 9 7 7 9 8
4 10 : 4 4 5 7 9 8 4 8 6 6 5 7 7 5 9 9 6 8
5 10 : 8 5 9 6 6 7 7 5 5 8 8 6 9 9 7
6 10 :
7 10 :
8 10 :
9 10 :
*/
vi naive5(int l, int r) {
vector<vector<tuple<int, int, int>>> ps(r);
int n = r;
rep(i, 3 * n) repi(j, i + 1, 3 * n - 1) repi(k, j + 1, 3 * n - 1) {
int d = abs((j - i) - (k - j)); // |i - 2j + k|
if (l <= d && d < r) ps[d].push_back({ i, j, k });
}
vi a(3 * n, -1);
function<bool(int)> rf = [&](int d) {
if (d == r) {
int mimi = 0;
rep(i, 3 * n) {
if (mimi == 0) {
if (a[i] == -1) mimi = 1;
}
else if (mimi == 1) {
if (a[i] != -1) mimi = 2;
}
else if (mimi == 2) {
if (a[i] == -1) mimi = 3;
}
}
if (mimi != 3) {
dump(a);
}
return false;
return mimi != 3;
}
repe(p, ps[d]) {
auto [i, j, k] = p;
if (a[i] != -1 || a[j] != -1 || a[k] != -1) continue;
a[i] = a[j] = a[k] = d;
if (rf(d + 1)) return true;
a[i] = a[j] = a[k] = -1;
}
return false;
};
if (!rf(l)) return vi();
return a;
}
/*
4 8
7 4 6 6 5 5 4 4 7 7 6 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
5 6 7 7 4 4 5 5 6 6 4 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 7 4 6 6 5 5 4 4 7 7 6 5
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 5 6 7 7 4 4 5 5 6 6 4 7
*/
void zikken5() {
repi(r, 1, 10) rep(l, r) {
dump(l, r, ":", naive5(l, r));
}
exit(0);
}
// 小さいケースに帰着する作戦は n:偶 でうまくいかなかったので，mod3 で分類する作戦にした．
vi solve(int n) {
if (n <= 5) return naive2(n);
vi a;
if (n % 3 == 0) {
for (int x = n - 2; x >= 0; x -= 3) {
a.push_back(x);
}
a.push_back(n - 1);
for (int x = (n - 2) % 3; x <= n - 2; x += 3) {
a.push_back(x);
a.push_back(x);
}
for (int x = n - 4; x >= 0; x -= 3) {
a.push_back(x);
}
a.push_back(n - 1);
a.push_back(n - 1);
for (int x = (n - 4) % 3; x <= n - 4; x += 3) {
a.push_back(x);
a.push_back(x);
}
for (int x = n - 3; x >= 0; x -= 3) {
a.push_back(x);
}
for (int x = (n - 3) % 3; x <= n - 3; x += 3) {
a.push_back(x);
a.push_back(x);
}
}
else if (n % 3 == 1) {
for (int x = n - 2; x >= 0; x -= 3) {
a.push_back(x);
}
a.push_back(n - 1);
a.push_back(n - 1);
for (int x = (n - 2) % 3; x <= n - 2; x += 3) {
a.push_back(x);
a.push_back(x);
}
for (int x = n - 3; x >= 0; x -= 3) {
a.push_back(x);
}
a.push_back(n - 1);
for (int x = (n - 3) % 3; x <= n - 3; x += 3) {
a.push_back(x);
a.push_back(x);
}
for (int x = n - 4; x >= 0; x -= 3) {
a.push_back(x);
}
for (int x = (n - 4) % 3; x <= n - 4; x += 3) {
a.push_back(x);
a.push_back(x);
}
}
else {
for (int x = n - 3; x >= 0; x -= 3) {
a.push_back(x);
}
a.push_back(n - 1);
a.push_back(n - 1);
for (int x = (n - 3) % 3; x <= n - 3; x += 3) {
a.push_back(x);
a.push_back(x);
}
for (int x = n - 4; x >= 4; x -= 3) {
a.push_back(x);
}
a.push_back(1);
a.push_back(1);
a.push_back(n - 1);
a.push_back(1);
for (int x = 4; x <= n - 4; x += 3) {
a.push_back(x);
a.push_back(x);
}
for (int x = n - 2; x >= 0; x -= 3) {
a.push_back(x);
}
for (int x = (n - 2) % 3; x <= n - 2; x += 3) {
a.push_back(x);
a.push_back(x);
}
}
return a;
}
int main() {
// input_from_file("input.txt");
// output_to_file("output.txt");
// naive4(7, 14); exit(0);
// zikken5();
int n;
cin >> n;
auto res = solve(n);
if (res.empty()) EXIT(-1);
rep(i, 3 * n) cout << res[i] << " \n"[i == 3 * n - 1];
}