Submission #1102231


Source Code Expand

import sys
sys.setrecursionlimit(1000000000)

def gcd(a: int, b:int):
    while b:
        a,b=b,a%b
    return a

def merge(a,us,vs):
    i,j,res=0,0,[]
    while i<len(us) and j<len(vs):
        if a[us[i]]>=a[vs[j]]:
            res.append(us[i])
            i+=1
        else:
            res.append(vs[j])
            j+=1
    return res+us[i:]+vs[j:]

def dfs(g,a,u,vis):
    vis[u]=True
    res=[]
    for v in g[u]:
        if not vis[v]:
            res=merge(a,res,dfs(g,a,v,vis))
    return [u]+res

while 1:
    try:
        n=int(input())
        a=sorted(map(int,input().split()))
    except: break

    g=[[] for _ in range(n)]
    for i in range(n):
        for j in range(i+1,n):
            if gcd(a[i],a[j])!=1:
                g[i].append(j)
                g[j].append(i)

    vis=[False]*n
    res=[]
    for u in range(n):
        if not vis[u]:
            res=merge(a,res,dfs(g,a,u,vis))
    print(' '.join(str(a[u]) for u in res))

Submission Info

Submission Time
Task E - Rearranging
User lyoz
Language PyPy3 (2.4.0)
Score 1600
Code Size 1003 Byte
Status AC
Exec Time 1209 ms
Memory 130012 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1600 / 1600
Status
AC × 2
AC × 47
Set Name Test Cases
Sample sample1.txt, sample2.txt
All sample1.txt, sample2.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in3.txt, in30.txt, in31.txt, in32.txt, in33.txt, in34.txt, in35.txt, in36.txt, in37.txt, in38.txt, in39.txt, in4.txt, in40.txt, in41.txt, in42.txt, in43.txt, in44.txt, in45.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt
Case Name Status Exec Time Memory
in1.txt AC 1209 ms 130012 KB
in10.txt AC 1177 ms 129500 KB
in11.txt AC 979 ms 83676 KB
in12.txt AC 974 ms 66396 KB
in13.txt AC 970 ms 83676 KB
in14.txt AC 981 ms 83676 KB
in15.txt AC 966 ms 66268 KB
in16.txt AC 1112 ms 121692 KB
in17.txt AC 1111 ms 121692 KB
in18.txt AC 1116 ms 121436 KB
in19.txt AC 1131 ms 121692 KB
in2.txt AC 1170 ms 126684 KB
in20.txt AC 1114 ms 121436 KB
in21.txt AC 787 ms 42972 KB
in22.txt AC 794 ms 43356 KB
in23.txt AC 801 ms 43356 KB
in24.txt AC 794 ms 43356 KB
in25.txt AC 786 ms 42972 KB
in26.txt AC 971 ms 83676 KB
in27.txt AC 978 ms 83804 KB
in28.txt AC 975 ms 83676 KB
in29.txt AC 987 ms 83932 KB
in3.txt AC 1165 ms 125404 KB
in30.txt AC 967 ms 66268 KB
in31.txt AC 199 ms 38256 KB
in32.txt AC 202 ms 38256 KB
in33.txt AC 201 ms 38256 KB
in34.txt AC 851 ms 42972 KB
in35.txt AC 851 ms 42844 KB
in36.txt AC 1021 ms 92124 KB
in37.txt AC 1021 ms 92124 KB
in38.txt AC 1031 ms 92380 KB
in39.txt AC 1029 ms 92380 KB
in4.txt AC 1166 ms 125404 KB
in40.txt AC 1016 ms 91868 KB
in41.txt AC 1015 ms 92124 KB
in42.txt AC 1045 ms 91996 KB
in43.txt AC 1068 ms 92380 KB
in44.txt AC 1038 ms 92124 KB
in45.txt AC 1030 ms 92252 KB
in5.txt AC 1174 ms 125276 KB
in6.txt AC 1185 ms 128092 KB
in7.txt AC 1176 ms 128092 KB
in8.txt AC 1183 ms 128732 KB
in9.txt AC 1166 ms 126044 KB
sample1.txt AC 200 ms 38256 KB
sample2.txt AC 217 ms 38256 KB