結果

問題 No.3506 All Distance is Square Number
コンテスト
ユーザー cho435
提出日時 2026-04-18 15:27:15
言語 C++23(gnu拡張)
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=gnu++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,146 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,874 ms
コンパイル使用メモリ 378,708 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-04-18 15:27:27
合計ジャッジ時間 9,230 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 WA * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define all(x) begin(x), end(x)
template <class T> bool chmin(T& x, T y) {
	return x > y ? (x = y, true) : false;
}
template <class T> bool chmax(T& x, T y) {
	return x < y ? (x = y, true) : false;
}

void solve() {
	int n;
	cin >> n;
	if (n == 2) {
		cout << "1\n1 2 1\n1 1\n";
		return;
	}
	if (n == 3) {
		cout << "3\n1 2 1\n1 3 1\n2 3 1\n";
		cout << "1 1\n1 2\n1 3\n";
		return;
	}
	if (n == 4) {
		cout << "4\n1 2 9\n2 3 16\n3 4 9\n4 1 16\n";
		cout << "1 1\n2 1 2\n1 4\n";
		cout << "1 2\n2 2 3\n1 3\n";
		return;
	}
	vector<vector<int>> g(n, vector<int>(n, -1));
	cout << n * 2 - 3 << '\n';
	{
		int cnt = 0;
		rep(i, 0, n) {
			if (i + 1 < n) {
				g[i][i + 1] = cnt;
				g[i + 1][i] = cnt;
				cnt++;
				cout << i + 1 << ' ' << i + 2 << ' ' << 1 << '\n';
			}
			if (i + 2 < n) {
				g[i][i + 2] = cnt;
				g[i + 2][i] = cnt;
				cnt++;
				cout << i + 1 << ' ' << i + 3 << ' ' << 1 << '\n';
			}
		}
	}
	vector<int> p2 = {1, 4, 9, 16, 25, 36, 49, 64, 81, 100};
	rep(st, 0, n) rep(ed, st + 1, n) {
		vector<int> v;
		if (ed - st <= 2) {
			v.push_back(g[st][ed]);
		} else if (ed - st == 3) {
			if (st == 0) {
				v.push_back(g[0][1]);
				v.push_back(g[1][2]);
				v.push_back(g[2][4]);
				v.push_back(g[4][3]);
			} else {
				v.push_back(g[st][st - 1]);
				v.push_back(g[st - 1][st + 1]);
				v.push_back(g[st + 1][st + 2]);
				v.push_back(g[st + 2][st + 3]);
			}
		} else {
			int cd = *prev(upper_bound(all(p2), ed - st));
			int m2 = (ed - st) - cd;
			int nw = st;
			rep(i, 0, m2) {
				v.push_back(g[nw][nw + 2]);
				nw += 2;
			}
			rep(i, m2, cd) {
				v.push_back(g[nw][nw + 1]);
				nw++;
			}
			assert(nw == ed);
		}
		assert(binary_search(all(p2), v.size()));
		for (int x : v) assert(x >= 0);
		// cout << st << " -> " << ed << " : ";
		cout << v.size();
		for (int x : v) cout << ' ' << x + 1;
		cout << " \n";
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(15);
	int t = 1;
	// cin >> t;
	while (t--) solve();
}
0