結果

問題 No.3506 All Distance is Square Number
コンテスト
ユーザー はじっこゆーれー
提出日時 2026-04-18 04:14:21
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 2,571 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 332 ms
コンパイル使用メモリ 85,120 KB
実行使用メモリ 82,560 KB
最終ジャッジ日時 2026-04-18 04:14:31
合計ジャッジ時間 6,030 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 WA * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
def solve():
    sys.setrecursionlimit(2000)
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    if N == 2:
        print("1")
        print("1 2 1")
        print("1\n1")
        return
    is_sq = [False] * 40001
    for i in range(1, 201):
        is_sq[i * i] = True
    P = [0] * (N + 1)
    used = [False] * 201
    for i in range(2, N + 1):
        P[i] = 2 * i - 3
        used[P[i]] = True
    E = [0] * (N + 1)
    avail_E = [x for x in range(2, 201, 2) if not used[x]]
    pref = [0] * (N + 1)
    for i in range(2, N + 1):
        pref[i] = pref[i-1] + P[i]
    def dfs(k):
        if k == N + 1:
            return True
        for e in avail_E:
            if used[e]: continue
            ok = True
            for i in range(2, k):
                if is_sq[pref[k] - pref[i]]:
                    continue
                if is_sq[pref[i] + e]:
                    continue
                if i >= 3 and is_sq[E[i] + e]:
                    continue
                if i >= 3 and is_sq[E[i] + pref[k]]:
                    continue
                ok = False
                break
            if ok:
                used[e] = True
                E[k] = e
                if dfs(k + 1):
                    return True
                used[e] = False
        return False
    dfs(3)
    edges = []
    edge_idx = {}
    for i in range(2, N + 1):
        edges.append((i - 1, i, P[i]))
        edge_idx[(i - 1, i)] = len(edges)
        edge_idx[(i, i - 1)] = len(edges)
    for i in range(3, N + 1):
        edges.append((1, i, E[i]))
        edge_idx[(1, i)] = len(edges)
        edge_idx[(i, 1)] = len(edges)
    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:
                path = [edge_idx[(m - 1, m)] for m in range(2, j + 1)]
            else:
                if is_sq[pref[j] - pref[i]]:
                    path = [edge_idx[(m - 1, m)] for m in range(i + 1, j + 1)]
                elif is_sq[pref[i] + E[j]]:
                    path = [edge_idx[(m, m - 1)] for m in range(i, 1, -1)] + [edge_idx[(1, j)]]
                elif i >= 3 and is_sq[E[i] + E[j]]:
                    path = [edge_idx[(i, 1)], edge_idx[(1, j)]]
                elif i >= 3 and is_sq[E[i] + pref[j]]:
                    path = [edge_idx[(i, 1)]] + [edge_idx[(m - 1, m)] for m in range(2, j + 1)]
            print(f"{len(path)} {' '.join(map(str, path))}")
solve()
0