Submission #1231337

---

Source Code Expand

import random
def tester(N=0):
	'''
	制約
1≦N≦2000
1≦Ai≦108
'''
	maxno1=2000
	maxno2=1e5
	s=input()
	if s!='':
		return(s)
	
	if N==0:
		return(2000)
		return(random.randint(2,maxno1))
	else:
		print('Testing...')
		print('N=',N)
		
		#return('2 3 4 6')
		
		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 = set()
	while i * i <= n:
		while n % i == 0:
			n //= i
			T.add(i)
		i += 1
	if n > 1:
		T.add(n)
	return(T)

import logging
import time



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

# create console handler and set level to debug
ch = logging.StreamHandler()
ch.setLevel(logging.WARNING)
#ch.setLevel(logging.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()]

start_time = time.time()

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]=factorint(A[i])
		
	for pn in F[i]:
		if pn not in P.keys():
			P[pn]=set()
		P[pn].add(i)

stepcount=1
logger.debug('Step %d: loss = %.2f (%.3f sec)' % (stepcount, 100, time.time() - start_time))

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

stepcount=2
logger.debug('Step %d: loss = %.2f (%.3f sec)' % (stepcount, 100, time.time() - start_time))

Ac=set(range(N))

stepcount=21
logger.debug('Step %d: loss = %.2f (%.3f sec)' % (stepcount, 100, time.time() - start_time))

Gc=copy.copy(G)
Tr=dict()

stepcount=22
logger.debug('Step %d: loss = %.2f (%.3f sec)' % (stepcount, 100, time.time() - start_time))


while len(Ac)>0:
	Tmp=[]
	rt=Ac.pop()
	me=rt
	Tmp.extend([me])
	
	while  len(Gc[me])>0:
		nxt=Gc[me].pop()
		if nxt in Ac:
			#Gc[nxt]=Gc[nxt]-{me}
			me=nxt
			Tmp.extend([me])
			Ac.remove(me)	
	
	Tr[rt]=Tmp

stepcount=3
logger.debug('Step %d: loss = %.2f (%.3f sec)' % (stepcount, 100, time.time() - start_time))

OoTr=list(Tr.keys())
OoTr.sort(reverse=True)

AnsIdx=[]
for i in OoTr:
	AnsIdx.extend(Tr[i])

stepcount=4
logger.debug('Step %d: loss = %.2f (%.3f sec)' % (stepcount, 100, time.time() - start_time))
	
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))))

stepcount=5
logger.debug('Step %d: loss = %.2f (%.3f sec)' % (stepcount, 100, time.time() - start_time))

logger.removeHandler(ch)

Submission Info

Judge Result