#include using namespace std; using Clock = chrono::steady_clock; constexpr int MAX_W = 300000; constexpr double TIME_LIMIT = 1.9; int edge_id(int n, int a, int b) { if (a > b) swap(a, b); if (b - a == n) return (a / n) * n + a % n; return n * (n - 1) + (a / n) * (n - 1) + a % n; } vector snake(int n) { vector p; for (int r = 0; r < n; ++r) { if (r % 2 == 0) for (int c = 0; c < n; ++c) p.push_back(r * n + c); else for (int c = n - 1; c >= 0; --c) p.push_back(r * n + c); } return p; } // 重複数を数え、同じ区間和を持つ [i,j), [k,l) も一組返す。 int analyze(const vector& w, array& dup, vector& freq, vector& owner, vector& touched) { int m = w.size() + 1; vector sum(m); for (int i = 0; i + 1 < m; ++i) sum[i + 1] = sum[i] + w[i]; int score = 0; touched.clear(); for (int j = 1; j < m; ++j) for (int i = 0; i < j; ++i) { int d = sum[j] - sum[i]; if (freq[d]) { if (score == 0) { int code = owner[d]; dup = {code / m, code % m, i, j}; } ++score; } else { owner[d] = i * m + j; touched.push_back(d); } ++freq[d]; } for (int d : touched) freq[d] = 0; return score; } void random_start(vector& w, mt19937& rng) { int m = w.size() + 1; vector marks(m); marks[0] = 0; do { for (int i = 1; i < m; ++i) marks[i] = 1 + rng() % (MAX_W - 1); sort(marks.begin(), marks.end()); } while (adjacent_find(marks.begin(), marks.end()) != marks.end()); for (int i = 0; i + 1 < m; ++i) w[i] = marks[i + 1] - marks[i]; } void output(int n, const vector& w) { int total = accumulate(w.begin(), w.end(), 0); vector ans(2 * n * (n - 1), total + 1); auto p = snake(n); for (int i = 0; i + 1 < (int)p.size(); ++i) ans[edge_id(n, p[i], p[i + 1])] = w[i]; int k = 0; for (int r = 0; r + 1 < n; ++r) { for (int c = 0; c < n; ++c) cout << (c ? " " : "") << ans[k++]; cout << '\n'; } for (int r = 0; r < n; ++r) { for (int c = 0; c + 1 < n; ++c) cout << (c ? " " : "") << ans[k++]; cout << '\n'; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; int m = n * n; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); vector w(m - 1), freq(MAX_W), owner(MAX_W), touched; touched.reserve((size_t)m * (m - 1) / 2); random_start(w, rng); int total = accumulate(w.begin(), w.end(), 0), steps = 0, stagnation = 0; auto deadline = Clock::now() + chrono::duration_cast(chrono::duration(TIME_LIMIT)); array d; int score = analyze(w, d, freq, owner, touched); while (Clock::now() < deadline) { if (score == 0) { output(n, w); return 0; } // 一方の区間だけに含まれる辺を変えれば、重複した二距離の片方だけが1変わる。 if (rng() & 1) { swap(d[0], d[2]); swap(d[1], d[3]); } vector candidate; for (int e = d[0]; e < d[1]; ++e) if (!(d[2] <= e && e < d[3])) candidate.push_back(e); if (candidate.empty()) { swap(d[0], d[2]); swap(d[1], d[3]); for (int e = d[0]; e < d[1]; ++e) if (!(d[2] <= e && e < d[3])) candidate.push_back(e); } int e = candidate[rng() % candidate.size()]; int delta = (rng() & 1) ? 1 : -1; if ((delta < 0 && w[e] == 1) || (delta > 0 && total == MAX_W - 1)) delta = -delta; if ((delta < 0 && w[e] == 1) || (delta > 0 && total == MAX_W - 1)) { random_start(w, rng); total = accumulate(w.begin(), w.end(), 0); score = analyze(w, d, freq, owner, touched); stagnation = 0; continue; } w[e] += delta; total += delta; array next_dup; int next_score = analyze(w, next_dup, freq, owner, touched); if (next_score < score || (next_score == score && rng() % 4 == 0)) { stagnation = next_score < score ? 0 : stagnation + 1; score = next_score; d = next_dup; } else { w[e] -= delta; total -= delta; ++stagnation; } ++steps; if (stagnation >= 5000) { random_start(w, rng); total = accumulate(w.begin(), w.end(), 0); score = analyze(w, d, freq, owner, touched); stagnation = 0; } } cout << -1 << '\n'; }