Submission #1227450

---

Source Code Expand

import random
def tester(N=0):
	'''
	制約
1≦N≦2000
1≦Ai≦108
'''
	maxno1=20
	maxno2=1e5
	s=input()
	if s!='':
		return(s)
	
	if N==0:
		#return(6)
		return(random.randint(2,maxno1))
	else:
		print('Testing...')
		print('N=',N)
		
		#return('1 2 3 4 5 2')
		
		A=[]
		for i in range(N):
			A.extend([random.randint(1,maxno2)])
		r=' '.join(list(map(str,A)))
		
		return(r)

def factorint(n):
	i = 2
	T = []
	while i * i <= n:
		while n % i == 0:
			n //= i
			T.append(i)
		i += 1
	if n > 1:
		T.append(n)
	return(T)

import logging

# create logger
logger = logging.getLogger('simple_example')
logger.setLevel(logging.WARNING)#DEBUG)

# create console handler and set level to debug
ch = logging.StreamHandler()
ch.setLevel(logging.WARNING) #DEBUG)

# create formatter
formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')

# add formatter to ch
ch.setFormatter(formatter)

# add ch to logger
logger.addHandler(ch)

import copy
N=int(tester())
A=[int(x) for x in tester(N).split()]
A.sort(reverse=False)
logger.debug('A is %s',str(A))

F=dict()
P=dict()
for i in range(N):
	if A[i]==1:
		F[i]={1}
	else:
		F[i]=set(factorint(A[i]))
	for y in F[i]:
		if y not in P.keys():
			P[y]=set()
		P[y].add(i)

G=dict()
for i in F.keys():
	G[i]=set()
	for y in F[i]:
		G[i]=G[i].union(P[y])
	G[i].remove(i)

Ac=list(range(N))
Gc=copy.deepcopy(G)
Tr=dict()
while len(Ac)>0:
	Tmp=[]
	rt=min(Ac)
	me=rt
	Tmp.extend([me])
	Ac.remove(me)
	while len(Gc[me])>0:
		nxt=min(Gc[me])
		if nxt not in Ac:
			Gc[me].remove(nxt)
			continue
		else:
			me=nxt
			Tmp.extend([me])
			Ac.remove(me)
	Tr[rt]=Tmp
	
OoTr=list(Tr.keys())
OoTr.sort(reverse=True)

AnsIdx=[]
for i in OoTr:
	AnsIdx.extend(Tr[i])
	
for i in range(N):
	for j in range(N-1,i,-1):
		if AnsIdx[j-1]<AnsIdx[j]:
			if F[AnsIdx[j-1]]&F[AnsIdx[j]]==set():
				AnsIdx[j-1],AnsIdx[j]=AnsIdx[j],AnsIdx[j-1]
	
Ans=[A[i] for i in AnsIdx]
print(' '.join(list(map(str,Ans))))

logger.removeHandler(ch)

Submission Info

Judge Result