Submission #1230842


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(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 = 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)#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()]

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]:
		G[i]=G[i].union(P[y])
	G[i]={k for k in G[i] if k>i}
	
	#G[i].remove(i)

stepcount=2
logger.debug('Step %d: loss = %.2f (%.3f sec)' % (stepcount, 100, time.time() - start_time))
'''
https://ja.m.wikipedia.org/wiki/トポロジカルソート

    
L ← トポロジカルソートされた結果の入る空の連結リスト

for each ノード n do
    visit(n)

function visit(Node n)
    if n をまだ訪れていなければ then
        n を訪問済みとして印を付ける
        for each n の出力辺 e とその先のノード m do
            visit(m)
        n を L の先頭に追加
'''
#bellow is a bottleneck
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

Submission Time
Task E - Rearranging
User Pgmto70
Language Python (3.4.3)
Score 0
Code Size 3389 Byte
Status WA
Exec Time 2107 ms
Memory 60636 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1600
Status
AC × 1
WA × 1
AC × 7
WA × 27
TLE × 15
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, sample1.txt, sample2.txt
Case Name Status Exec Time Memory
in1.txt TLE 2101 ms 42092 KB
in10.txt TLE 2085 ms 44168 KB
in11.txt WA 1493 ms 12832 KB
in12.txt WA 1478 ms 11036 KB
in13.txt WA 1511 ms 10784 KB
in14.txt WA 1495 ms 10800 KB
in15.txt WA 1441 ms 10836 KB
in16.txt TLE 2071 ms 59128 KB
in17.txt TLE 2043 ms 59448 KB
in18.txt TLE 2044 ms 60636 KB
in19.txt TLE 2070 ms 58476 KB
in2.txt TLE 2077 ms 42508 KB
in20.txt TLE 2061 ms 59048 KB
in21.txt WA 584 ms 7092 KB
in22.txt WA 744 ms 7108 KB
in23.txt WA 616 ms 7112 KB
in24.txt WA 585 ms 7116 KB
in25.txt WA 572 ms 7092 KB
in26.txt WA 1446 ms 10908 KB
in27.txt WA 1488 ms 10928 KB
in28.txt WA 1456 ms 10908 KB
in29.txt WA 1467 ms 11100 KB
in3.txt TLE 2091 ms 41752 KB
in30.txt WA 1532 ms 11044 KB
in31.txt AC 33 ms 4668 KB
in32.txt AC 34 ms 4668 KB
in33.txt AC 33 ms 4652 KB
in34.txt AC 620 ms 7204 KB
in35.txt AC 668 ms 7220 KB
in36.txt WA 1512 ms 17864 KB
in37.txt WA 1555 ms 17816 KB
in38.txt WA 1554 ms 17820 KB
in39.txt WA 1499 ms 17896 KB
in4.txt TLE 2078 ms 41672 KB
in40.txt WA 1496 ms 17772 KB
in41.txt WA 1496 ms 17788 KB
in42.txt WA 1540 ms 17800 KB
in43.txt WA 1572 ms 17948 KB
in44.txt WA 1500 ms 17856 KB
in45.txt WA 1542 ms 17912 KB
in5.txt TLE 2043 ms 41704 KB
in6.txt TLE 2107 ms 43096 KB
in7.txt TLE 2071 ms 44708 KB
in8.txt TLE 2056 ms 44044 KB
in9.txt TLE 2106 ms 41584 KB
sample1.txt AC 33 ms 4668 KB
sample2.txt WA 33 ms 4668 KB