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

• 問題: No.3506 All Distance is Square Number
• ユーザー: Kurao
• 提出日時: 2026-04-18 17:32:00
• 言語: PyPy3 (7.3.17)
• 結果: RE
• 実行時間: -
• コード長: 3,971 bytes
• コンパイル時間: 312 ms
• コンパイル使用メモリ: 85,248 KB
• 実行使用メモリ: 307,584 KB
• 最終ジャッジ日時: 2026-04-18 17:33:18
• 合計ジャッジ時間: 26,174 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge1_1

ファイルパターン	結果
other	WA * 15 RE * 9 TLE * 5

ソースコード

#--------------------------------------------------
import sys
import functools
#sys.setrecursionlimit(10**9)
#codon↓--------------------------------------------
_factorial=[1]
def factorial(n):
    while len(_factorial)<=n:
        _factorial.append((_factorial[-1]*len(_factorial))%mod)
    return _factorial[n]

def binom(n,r):
    if r>=mod:
        raise ValueError("r is too big")
    if n<0:
        return 0
    if r>n:
        return 0
    if r<0:
        return 0
    ans=((factorial(n)*pow(factorial(r),mod-2,mod))%mod*pow(factorial(n-r),mod-2,mod))%mod
    return ans

import string
import itertools
alp_low=list(string.ascii_lowercase)
alp_up=list(string.ascii_uppercase)
dij=[[0,1],[1,0],[0,-1],[-1,0]]

mod=998244353
INF=10**18
def dijkstra(edges, num_node,start):
    """

    [node_num,weight>0][
    
    (example)

    Edges = [
        [[1, 4], [2, 3]],
        [[0, 1], [3, 1]],
        [[3, 2]],
        [],
    ]
    """
    import heapq;n=[INF]*num_node;n[start]=0;n_name=[];heapq.heappush(n_name,[0,start])
    while len(n_name):
        _,min_p=heapq.heappop(n_name)
        for f in edges[min_p]:
            g,c=f
            if n[min_p]+c<n[g]:n[g]=n[min_p]+c;heapq.heappush(n_name,[n[min_p]+c,g])
    return n

def nin():
    return list(map(int,input().split()))
def deq(x):
    return [i-1 for i in x]
def pop_cnt(n):
    ans=0
    while n:
        if n%2:
            ans+=1
        n//=2
    return ans

def main():
    n,=nin()
    if n>=19:
        size1=size2=8
    elif 11<=n<19:
        size1=size2=(n-3)//2
    else:
        if 9<=n<=10:
            size1=2
            size2=4
        else:
            size1=size2=2
    if size1==size2:
        pat1=[1,2,3,5,4,8,6,14,7,23,9,41,10,74,11,137][:size1*2]
        off=1
        while len(set(pat1)&set(i+off for i in pat1))>0:
            off+=1
        pat2=[i+off for i in pat1]
    else:
        pat1=[1,2,3,5,4,8,6,14,7,23,9,41,10,74,11,137][:size1*2]
        pat2=[1,2,3,5,4,8,6,14,7,23,9,41,10,74,11,137][size1*2:size2*2+size1*2]

    print(n,n+size1+size2)
    v=[[[] for j in range(n)] for i in range(n)]
    for i in range(size1):
        print(i+1,i+2,pat1[i*2])#,2*i)
        print(i+1,i+2,pat1[i*2+1])#,2*i+1)
        v[i][i+1].append((pat1[i*2],2*i))
        v[i][i+1].append((pat1[i*2+1],2*i+1))
        v[i+1][i].append((pat1[i*2],2*i))
        v[i+1][i].append((pat1[i*2+1],2*i+1))
    for i in range(size2):
        print(size1+i+1,size1+i+2,pat2[i*2])#,2*size+2*i)
        print(size1+i+1,size1+i+2,pat2[i*2+1])#,2*size+2*i+1)
        v[size1+i][size1+i+1].append((pat2[i*2],2*size1+i*2))
        v[size1+i][size1+i+1].append((pat2[i*2+1],2*size1+i*2+1))
        v[size1+i+1][size1+i].append((pat2[i*2],2*size1+i*2))
        v[size1+i+1][size1+i].append((pat2[i*2+1],2*size1+i*2+1))
    use=set(range(1,201))^set(pat1)^set(pat2)
    use=sorted(list(use))
    for i in range(size1+size2,n):
        print(i+1,(i+1)%n+1,use[i-size1-size2])#,i+size*2)
        v[i][(i+1)%n].append((use[i-size1-size2],i+size1+size2))
        v[(i+1)%n][i].append((use[i-size1-size2],i+size1+size2))
        
    hei=set([i**2 for i in range(400)])
    def search(i,j):
        now_sets=[{0:(-1,0)}]
        now=i
        while now!=j:
            new={}
            for w,no in v[now][(now+1)%n]:
                for ii in now_sets[-1]:
                    new[ii+w]=(no,w)
            now_sets.append(new)
            now+=1
            now%=n
        for i in now_sets[-1]:
            if i in hei:
                ans=[now_sets[-1][i][0]]
                while len(now_sets)>1:
                    i-=now_sets[-1][i][1]
                    now_sets.pop(-1)
                    ans.append(now_sets[-1][i][0])
                return ans[::-1][1:]
    
    for i in range(n):
        for j in range(i+1,n):
            ans=search(i,j)
            if ans==None:
                ans=search(j,i)[::-1]
            print(len(ans),*[i+1 for i in ans])

if __name__=="__main__":
    main()