結果
| 問題 | No.3506 All Distance is Square Number |
| コンテスト | |
| ユーザー |
 はじっこゆーれー
|
| 提出日時 | 2026-04-18 02:57:26 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,571 bytes |
| 記録 | |
| コンパイル時間 | 459 ms |
| コンパイル使用メモリ | 85,220 KB |
| 実行使用メモリ | 88,112 KB |
| 最終ジャッジ日時 | 2026-04-18 02:58:17 |
| 合計ジャッジ時間 | 46,221 ms |
|
ジャッジサーバーID （参考情報） |
judge1_1 / judge3_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 8 WA * 21 |
ソースコード
import sys
import random
import time
def solve():
start_time = time.time()
input_data = sys.stdin.read().split()
if not input_data:
return
N = int(input_data[0])
is_sq = [False] * 40001
for i in range(1, 201):
is_sq[i * i] = True
best_P = [0] * (N + 1)
best_E = [0] * (N + 1)
max_k = 0
while time.time() - start_time < 1.8:
used = [False] * 201
E = [0] * (N + 1)
P = [0] * (N + 1)
pref = [0] * (N + 1)
avail = list(range(1, 201))
random.shuffle(avail)
E[2] = 0
for w in avail:
if is_sq[w]:
E[2] = w
break
if E[2] == 0:
continue
used[E[2]] = True
k = 3
while k <= N:
if time.time() - start_time > 1.8:
break
curr_avail = [w for w in range(1, 201) if not used[w]]
random.shuffle(curr_avail)
found = False
for p in curr_avail:
for e in curr_avail:
if p == e:
continue
ok1 = False
if is_sq[e]:
ok1 = True
else:
for x in range(2, k):
if is_sq[E[x] + pref[k-1] + p - pref[x]]:
ok1 = True
break
if not ok1:
continue
all_ok = True
for i in range(2, k):
oki = False
if is_sq[pref[k-1] + p - pref[i]]:
oki = True
else:
for x in range(2, k):
if is_sq[abs(pref[i] - pref[x]) + E[x] + e]:
oki = True
break
if not oki:
all_ok = False
break
if all_ok:
P[k] = p
E[k] = e
pref[k] = pref[k-1] + p
used[p] = True
used[e] = True
found = True
break
if found:
break
if not found:
break
k += 1
if k - 1 > max_k:
max_k = k - 1
best_P = list(P)
best_E = list(E)
if max_k == N:
break
P = best_P
E = best_E
used = [False] * 201
for i in range(2, max_k + 1):
if E[i] > 0:
used[E[i]] = True
if P[i] > 0:
used[P[i]] = True
unused = [w for w in range(1, 201) if not used[w]]
idx = 0
for i in range(2, N + 1):
if E[i] == 0:
E[i] = unused[idx]
idx += 1
if i >= 3 and P[i] == 0:
P[i] = unused[idx]
idx += 1
pref = [0] * (N + 1)
for i in range(3, N + 1):
pref[i] = pref[i-1] + P[i]
edges = []
edge_idx = {}
edges.append((1, 2, E[2]))
edge_idx[(1, 2)] = 1
edge_idx[(2, 1)] = 1
e_cnt = 2
for k in range(3, N + 1):
edges.append((1, k, E[k]))
edge_idx[(1, k)] = e_cnt
edge_idx[(k, 1)] = e_cnt
e_cnt += 1
edges.append((k - 1, k, P[k]))
edge_idx[(k - 1, k)] = e_cnt
edge_idx[(k, k - 1)] = e_cnt
e_cnt += 1
print(len(edges))
for u, v, c in edges:
print(f"{u} {v} {c}")
for i in range(1, N):
for j in range(i + 1, N + 1):
path = []
if i == 1:
if is_sq[E[j]]:
path = [edge_idx[(1, j)]]
else:
for x in range(2, j):
if is_sq[E[x] + pref[j] - pref[x]]:
path = [edge_idx[(1, x)]]
for m in range(x + 1, j + 1):
path.append(edge_idx[(m - 1, m)])
break
else:
if is_sq[pref[j] - pref[i]]:
for m in range(i + 1, j + 1):
path.append(edge_idx[(m - 1, m)])
else:
for x in range(2, j):
dist = abs(pref[i] - pref[x]) + E[x] + E[j]
if is_sq[dist]:
if x <= i:
for m in range(i, x, -1):
path.append(edge_idx[(m, m - 1)])
else:
for m in range(i + 1, x + 1):
path.append(edge_idx[(m - 1, m)])
path.append(edge_idx[(x, 1)])
path.append(edge_idx[(1, j)])
break
if not path:
if i == 1:
path = [edge_idx[(1, j)]]
else:
path = [edge_idx[(i, 1)], edge_idx[(1, j)]]
print(f"{len(path)} {' '.join(map(str, path))}")
if __name__ == '__main__':
solve()