#1159093 (PyPy3) No.3506 All Distance is Square Number

• 問題: No.3506 All Distance is Square Number
• ユーザー: はじっこゆーれー
• 提出日時: 2026-04-18 04:18:52
• 言語: PyPy3 (7.3.17)
• 結果: WA
• 実行時間: -
• コード長: 3,930 bytes
• コンパイル時間: 236 ms
• コンパイル使用メモリ: 85,376 KB
• 実行使用メモリ: 117,048 KB
• 最終ジャッジ日時: 2026-04-18 04:19:12
• 合計ジャッジ時間: 16,372 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_1

ファイルパターン	結果
other	AC * 25 WA * 4

ソースコード

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
    if N == 2:
        print("1")
        print("1 2 1")
        print("1\n1")
        return
    P = [0] * N
    for k in range(2, N):
        P[k] = 2 * k - 1
    pref = [0] * (N + 1)
    for k in range(3, N + 1):
        pref[k] = pref[k-1] + P[k-1]
    def dist_outer(u, v):
        if u > v:
            u, v = v, u
        return pref[v] - pref[u]
    def get_path_nodes(start, end):
        if start <= end:
            return list(range(start, end + 1))
        else:
            return list(range(start, end - 1, -1))
    avail_even = [x for x in range(2, 201, 2)]
    while time.time() - start_time < 1.8:
        random.shuffle(avail_even)
        E = [0] * (N + 1)
        for i in range(3, N + 1):
            E[i] = avail_even[i - 3]
        def weight_1(x):
            if x == 2: return 1
            return E[x]
        dist_v_T = [[0] * (N + 1) for _ in range(N + 1)]
        for v in range(2, N + 1):
            for T in range(2, N + 1):
                dist_v_T[v][T] = weight_1(v) + dist_outer(v, T)
        all_found = True
        ans_paths = {}
        for T in range(2, N + 1):
            found = False
            for v in range(2, N + 1):
                if is_sq[dist_v_T[v][T]]:
                    ans_paths[(1, T)] = [1] + get_path_nodes(v, T)
                    found = True
                    break
            if not found:
                all_found = False
                break
        if not all_found:
            continue
        for S in range(2, N):
            for T in range(S + 1, N + 1):
                found = False
                d = dist_outer(S, T)
                if is_sq[d]:
                    ans_paths[(S, T)] = get_path_nodes(S, T)
                    found = True
                    continue
                for u in range(2, N + 1):
                    min1, max1 = (S, u) if S < u else (u, S)
                    d_u = dist_outer(S, u) + weight_1(u)
                    for v in range(2, N + 1):
                        if u == v: continue
                        min2, max2 = (v, T) if v < T else (T, v)
                        if max1 < min2 or max2 < min1:
                            if is_sq[d_u + dist_v_T[v][T]]:
                                ans_paths[(S, T)] = get_path_nodes(S, u) + [1] + get_path_nodes(v, T)
                                found = True
                                break
                    if found:
                        break
                if not found:
                    all_found = False
                    break
            if not all_found:
                break
        if all_found:
            edges = []
            edge_idx = {}
            edges.append((1, 2, 1))
            edge_idx[(1, 2)] = 1
            edge_idx[(2, 1)] = 1
            idx = 2
            for k in range(2, N):
                edges.append((k, k + 1, P[k]))
                edge_idx[(k, k + 1)] = idx
                edge_idx[(k + 1, k)] = idx
                idx += 1
            for v in range(3, N + 1):
                edges.append((1, v, E[v]))
                edge_idx[(1, v)] = idx
                edge_idx[(v, 1)] = idx
                idx += 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):
                    nodes = ans_paths[(i, j)]
                    e_path = []
                    for k in range(len(nodes) - 1):
                        e_path.append(edge_idx[(nodes[k], nodes[k+1])])
                    print(f"{len(e_path)} {' '.join(map(str, e_path))}")
            return
if __name__ == '__main__':
    solve()