結果
| 問題 | No.3506 All Distance is Square Number |
| コンテスト | |
| ユーザー |
 Kude
|
| 提出日時 | 2026-04-18 12:31:20 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
AC
|
| 実行時間 | 122 ms / 2,000 ms |
| コード長 | 6,531 bytes |
| 記録 | |
| コンパイル時間 | 450 ms |
| コンパイル使用メモリ | 85,364 KB |
| 実行使用メモリ | 85,988 KB |
| 最終ジャッジ日時 | 2026-04-18 12:31:34 |
| 合計ジャッジ時間 | 9,926 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge2_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 29 |
ソースコード
from math import isqrt
memo = [([(0,1,1)],[[0]]),([(0,1,7),(0,2,9),(0,1,1)],[[2],[1],[0,1]]),([(1,3,12),(0,3,7),(1,2,4),(0,2,9),(2,3,5)],[[1,4,2],[3],[3,2,0],[2],[2,4],[3,1]]),([(2,3,1),(0,3,4),(0,1,9),(0,4,12),(2,4,11),(0,2,2),(3,4,3)],[[2],[3,6,0],[1],[1,0,4],[2,3,6,0],[2,5,4,6],[2,1,6],[0],[0,6],[1,3]]),([(3,4,1),(1,2,9),(3,5,15),(2,4,8),(0,4,3),(1,5,11),(0,5,5),(2,5,12),(0,3,7)],[[8,0,3,1],[8,0,3],[4,0],[6,7,3],[8,0,3,1,5],[1],[1,7,2],[5,2,8,4],[1,3,4,6],[3,0],[7,6,8,0],[3,4,6],[0],[0,4,6],[0,2]]),([(4,6,3),(4,5,6),(3,5,4),(1,2,9),(0,3,1),(2,3,14),(1,6,15),(0,6,8),(2,4,11),(3,6,2),(0,5,7)],[[10,2,9,0,8,3],[10,2,5],[4],[10,2,5,8],[7,6,3,8,1],[10,2,5,3,6],[3],[3,8,0,9],[6,7,4,5,8],[6,9,4,10],[3,5,9],[8,1,10,4],[5,2,10,7,0],[5,9,0,1],[5,9],[5,8],[2],[4,7],[0,9,2],[1,10,4,9],[1,0]]),([(3,5,11),(2,4,8),(1,4,4),(1,7,1),(1,5,21),(6,7,12),(0,6,9),(2,5,15),(1,6,17),(3,4,13),(2,7,10),(0,4,5),(0,6,7)],[[11,2],[12,8,2,1],[6,8,2,1,7,0],[12,5,3,4,7,1],[6,5,3,2,1,7],[6],[12,8,3],[4,7],[2,11,12,5,10,7,0],[2],[3,5,12,11,9,0],[2,11,12],[3],[10,5,6,11,9],[10,5,6,11],[10,3,8,12,11,9,0],[1,2,3,5],[7,4,2,11,12,5],[0,4,2],[9,1,7],[9,11,12],[0,7,10],[2,4],[1,10,3,8],[9,0,7,10],[0,9,11,12],[7,10],[6,11,2,4,7,10]]),([(6,7,5),(6,8,14),(2,4,15),(1,8,13),(3,7,20),(4,8,17),(0,3,18),(2,5,4),(3,4,9),(0,6,12),(1,7,2),(3,5,16),(5,7,1),(2,8,3),(1,7,22)],[[6,8,2,7,12,10],[6,8,5,3,10,12,7],[9,1,13,7,11],[9,0,10,3,5],[6,8,2,13,3,14,12],[6,8,5,3,10,0],[6,8,2,13,1,0],[9,0,4,8,2,13],[14,0,9,6,8,2],[3,13,7,11],[14,12,11,6,9,1,5],[3,5,2,7],[10,12,11,6,9],[3,5,2,7,11,6,9,0],[10,4,8,2,13],[7,12,4],[7,12,0,9,6,8],[7],[2,8,4,0],[13,5,8,4],[7,11,6,9,1],[8],[11],[4,0],[6,9,1,5,2,7,12],[8,2,7,12,14,3],[8,11],[2,7,12,0],[5,13,7,12],[8,4,14,3],[7,2,5,3,14,4,6,9],[12],[7,2,5],[1,3,14],[0,12,11,8,2,13],[4,6,9,1]]),([(0,6,13),(1,2,12),(3,5,16),(3,7,7),(2,8,15),(2,9,1),(4,5,3),(0,7,10),(7,8,4),(3,8,5),(5,8,20),(5,9,9),(1,7,2),(3,5,11),(1,5,21),(3,4,18),(6,9,6)],[[7,3,13,14],[7,12,14,13,9,4],[7,12,14,2],[7,12,14,6],[0,16,5,1,12,8,9,15,6],[7,8,4,5,16],[0,16,5,1,14,6,15,3],[7,12,14,13,9],[7,12,1,5],[12,8,10,11,5],[12,3],[14,10,9,15],[12,3,2],[12,7,0],[14,6,15,3],[1,5,11,2,3,8],[12,8,9,2,11],[1,14,2],[1,14,6],[4,9,2],[4,10,14,12,7,0],[4,9,15,6,14,12],[1,14,13,9],[5],[9,8,12,1,5,11,6],[2],[15,6,11,16],[9,8],[2,10],[2,11],[15,3,8,10],[6,14,12,7,0],[15,3],[15,13,10],[6,13,3,12,1,5],[6,15,3,12,1,5,16],[10,4,1,12],[13,9],[11],[16,5,1,14,10,8],[16,11,2,9],[0,7,8,10,14,1,5],[8],[3,15,6,10,4,5],[4,5]]),([(9,10,6),(2,3,24),(5,8,2),(8,9,19),(4,5,10),(1,10,4),(3,7,1),(1,2,9),(0,3,17),(6,9,25),(1,4,11),(3,5,16),(5,9,26),(1,6,14),(0,10,7),(0,6,21),(1,6,23),(7,9,13),(0,4,12)],[[15,9,12,11,1,7],[18,10,13,9,17,6,1],[15,16,10,4,11],[8,6,17,9,13,10],[8,6,17,9,16,10,4],[8,1,7,13],[18,4,12,9,13,7,1,6],[18,10,13,9,3],[8,11,4,10,5,0],[18,4,12,9,16,5],[7],[13,9,12,11],[5,0,12,11,8,18],[7,1,11],[7,1,11,12,9],[16,15,18,4,2,3,17],[10,18,14,0,12,2],[10,4,11,8,15,9],[5],[7,10,18,8],[7,16,9,17,6,8,18],[1,6,17,12],[7,10,4,12,9],[1,6],[1,6,17,9,13,10,4,2],[1,11,4,10,13,9],[1,11,12,9,16,10,18,14],[11,12,9,15,18],[11],[1,7,10,4,2,3,9],[6],[1,7,16,9,3],[1,7,16,9],[1,7,10,4,2,3,0],[18,8,6,17,3,2],[10,13],[10,13,15,8,6],[10,13,15,8,11,2],[4,12],[18,15,9,0],[11,1,7,5,14,15],[4,18,15,16,7,1,6],[11,6,17,3],[4,18,14,5,16,9],[4,10,5],[16,10,18,8,6],[16,10,18,8,11,2],[9],[15,8,11,2,3,0],[6,1,7,10,4,12,3],[6,1,7,10,4,12],[6,8,14],[2,11,8,15,9],[2,11,1,7,10,18,14],[9,15,8,1,7,5]]),([(2,11,6),(5,9,17),(0,8,3),(2,3,9),(1,9,4),(4,10,14),(2,8,11),(3,4,13),(6,9,1),(2,5,25),(7,9,26),(4,8,21),(7,11,29),(0,4,19),(2,4,8),(2,4,10),(6,10,15),(8,11,28),(0,5,2),(6,11,24),(7,8,27)],[[13,15,0,19,8,4],[18,1,8,16,5,11,6],[13,14,3],[18,9,3,7],[2,20,10,8,16,5,15,9],[18,9,14,5,16],[2,11,14,9,1,10],[18,1,8,19,0,15,11],[13,5,16,8],[18,9,14,5],[2,6,9,1,8,19],[4,1,18,13,7,3],[4,1,18,2,11,14,3],[4,8,19,0,9,18,13],[4,8,16,5,7,3,9],[4,1,9,3,7,11,20,12,19],[4,1,9,0,12],[4,8,19,0,14,11],[4],[4,8,19,0,6,11,5],[4,1,9,3,7,5,16,19],[3],[9,1,8,19,12,20,11],[9],[15,13,18,1,8],[14,5,16,8,10],[0,19,16,5,13,2],[6,20,10],[3,7,5],[3,7,13,2,20,12],[3,9,1,8,16,5],[3,6,2,18],[7,14,9,1,8],[3,14,13,18,1,10],[3,14,5,16,8,10,20],[3,15,5,16,8],[7,15,9,1,8,16],[7,15,9,18,2,17],[15,0,17,2,18],[11,2,18,9,0,19],[13,2,20],[13,18,1,10,12,17],[7,3,9,1],[7,3,9,18,2,20,10,8,16],[15,0],[9,15,5,16],[9,14,11,20],[9,6],[9,3,7,11,20,10],[9,15,5],[18,13,7,3,0],[8,1,9,6,20],[16,5,7,3,9,18,2],[8],[8,1,18,2,17,0,15,5],[8,1,9,0],[10,1,9,15,13,2],[20,2,18,1],[20,2,18,9,15,5],[20,11,15,0],[6,14,5,16,8],[2,13,5],[2,13,14,0],[1,9,14,5],[8,19],[5,13,2,17]])]
def solve(n):
if n <= 12: return memo[n-2]
state = [1] * 201
state[0] = 0
k = 0
while 2 ** k < n:
k += 1
k = min(k + 1, 8, (n - 3) // 2)
g = [[] for _ in range(n)]
es = []
for i in range(n):
if i < 2 * k:
d = 2 ** (i % k)
p = 0
while not state[p] or not state[p + d]:
p += 1
g[i].append(len(es))
es.append((i, (i + 1) % n, p))
g[i].append(len(es))
es.append((i, (i + 1) % n, p + d))
state[p] = state[p + d] = 0
else:
p = 0
while not state[p]:
p += 1
g[i].append(len(es))
es.append((i, (i + 1) % n, p))
state[p] = 0
paths = []
def f(u, v):
path = []
cand = [(-1, -1)] * k
if min(v, 2*k) - min(u, 2*k) >= k:
sm = 0
while u != v:
eid = g[u][0]
sm += es[eid][2]
if u < 2 * k:
cand[u%k] = (len(path), g[u][1])
path.append(eid)
u += 1
else:
sm = 0
while u != v:
u = (u + n - 1) % n
eid = g[u][0]
sm += es[eid][2]
if u < 2 * k:
cand[u%k] = (len(path), g[u][1])
path.append(eid)
todo = (isqrt(sm - 1) + 1) ** 2 - sm
for i in range(k)[::-1]:
p, eid = cand[i]
assert p != -1
if todo >= 1 << i:
todo -= 1 << i
path[p] = eid
assert todo == 0
paths.append(path)
return
for i in range(n):
for j in range(i + 1, n):
f(i, j)
return (es, paths)
es, paths = solve(int(input()))
print(len(es))
for u, v, w in es:
print(u + 1, v + 1, w)
for p in paths:
print(len(p), *(i + 1 for i in p))