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 |
|
|
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 |