Problem:


Score : 1600 points

Problem Statement

There are N integers written on a blackboard. The i-th integer is A_i.

Takahashi and Aoki will arrange these integers in a row, as follows:

First, Takahashi will arrange the integers as he wishes.

Then, Aoki will repeatedly swap two adjacent integers that are coprime, as many times as he wishes.

We will assume that Takahashi acts optimally so that the eventual sequence will be lexicographically as small as possible, and we will also assume that Aoki acts optimally so that the eventual sequence will be lexicographically as large as possible.
Find the eventual sequence that will be produced.

Constraints

1 ≦ N ≦ 2000

1 ≦ A_i ≦ 10^8

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 … A_N

Output

Print the eventual sequence that will be produced, in a line.

Sample Input 1

5
1 2 3 4 5

Sample Output 1

5 3 2 4 1

If Takahashi arranges the given integers in the order (1,2,3,4,5), they will become (5,3,2,4,1) after Aoki optimally manipulates them.

Sample Input 2

4
2 3 4 6

Sample Output 2

2 4 6 3



Sample input:
5
1 2 3 4 5


Sample output:
5 3 2 4 1

Submission status: Wrong Answer

Solution code:
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 status: Wrong Answer

Solution code:
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 status: Wrong Answer

Solution code:
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 status: Wrong Answer

Solution code:
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 = []
	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])
Ans=[A[i] for i in AnsIdx]
print(' '.join(list(map(str,Ans))))

logger.removeHandler(ch)

Submission status: Wrong Answer

Solution code:
import random
def tester(N=0):
	maxno1=10
	maxno2=1e2
	s=input()
	if s!='':
		return(s)
	
	if N==0:
		return(5)
		return(random.randint(2,maxno1))
	else:
		print('Testing...')
		print('N=',N)
		
		return('1 2 3 4 5')
		
		A=[]
		for i in range(N):
			A.extend([random.randint(1,maxno2)])
		r=' '.join(list(map(str,A)))
		print(r)
		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.DEBUG)

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

# 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 x in A:
	if x==1:
		F[1]={1}
	else:
		F[x]=set(factorint(x))
	for y in F[x]:
		if y not in P.keys():
			P[y]=set()
		P[y].add(x)

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

Ac=copy.deepcopy(A)
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)

Ans=[]
for x in OoTr:
	Ans.extend(Tr[x])

print(' '.join(list(map(str,Ans))))

(logger).removeHandler(ch)

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
    return gcd(b,a%b) if b else 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=[[j for j in range(n) if i!=j and gcd(a[i],a[j])!=1] for i in range(n)]
    #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 status: Time Limit Exceeded

Solution code:
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 status: Time Limit Exceeded

Solution code:
def gcd(a,b):
    return gcd(b,a%b) if b else 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=[[j for j in range(n) if i!=j and gcd(a[i],a[j])!=1] for i in range(n)]
    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 status: Runtime Error

Solution code:
import random
def tester(N=0):
	maxno1=10
	maxno2=1e2
	s=input()
	if s!='':
		return(s)
	
	if N==0:
		return(6)
		return(random.randint(2,maxno1))
	else:
		print('Testing...')
		print('N=',N)
		
		return('2 3 4 5 6 25')
		
		A=[]
		for i in range(N):
			A.extend([random.randint(1,maxno2)])
		r=' '.join(list(map(str,A)))
		print(r)
		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.DEBUG)

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

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

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

Ac=copy.deepcopy(A)
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)

Ans=[]
for x in OoTr:
	Ans.extend(Tr[x])

print(' '.join(list(map(str,Ans))))

(logger).removeHandler(ch)

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()


def main():
    n = II()
    a = LI()
    a.sort()
    i = n-1
    m = {}
    def g(a,b):
        if (a,b) in m:
            return m[(a,b)]
        c = math.gcd(a,b)
        if c == 1:
            m[(a,b)] = True
        else:
            m[(a,b)] = False
        return c == 1

    def f(i):
        ai = a[i]
        ii = i
        ff = False
        while ii > 0:
            j = ii-1
            aj = a[j]
            mj = ii
            while g(ai,a[j]) and j >= 0:
                if a[j] < ai:
                    mj = j
                j -= 1
            if mj != ii:
                a[mj:ii+1] = [ai] + a[mj:ii]
                ff = True
                ii = mj
            else:
                if f(ii-1):
                    continue
                else:
                    break
        return ff

    for i in range(n-1,-1,-1):
        while f(i):
            pass
    sa = a[:]
    for _ in range(100):
        random.shuffle(a)
        for i in range(n-1,-1,-1):
            while f(i):
                pass
        if a < sa:
            sa = a[:]

    return ' '.join(map(str, sa))

print(main())