Submission #40746170

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN=2010;
int n,a[MAXN];

vector<int>e[MAXN],g[MAXN],S[MAXN];

int deg[MAXN];

struct DSU{
	int fa[MAXN];
	void init(int n){iota(fa+1,fa+1+n,1);}
	int find(int x){return (fa[x]==x)?(x):(fa[x]=find(fa[x]));}
	void merge(int x,int y){fa[find(x)]=find(y);}
}dsu;

void link(int x,int y){
	dsu.merge(x,y);
	e[x].push_back(y);e[y].push_back(x);
}
void glink(int x,int y){
	g[x].push_back(y);deg[y]++;
}

int dfn[MAXN],dtot;

void dfs(int u){
	dfn[u]=++dtot;
	for(auto v:e[u]){
		if(!dfn[v]){
			dfs(v);
		}
	}
}
void pre_solve(int x){
	int rt=S[x][0];
	for(auto u:S[x])if(a[u] < a[rt])rt=u;

	dfs(rt);

	for(auto u:S[x])for(auto v:e[u])if(u<v){
		if(dfn[u] < dfn[v])glink(u,v);
		else glink(v,u);
	}
}


priority_queue<int>pq;


int ans[MAXN],cur;

int main(){
	cin>>n;
	dsu.init(n);

	rep(i,1,n)cin>>a[i];
	sort(a+1,a+1+n);

	rep(i,1,n)rep(j,i+1,n){
		if(__gcd(a[i],a[j]) > 1){
			link(i,j);
		}
	}

	rep(i,1,n)S[dsu.find(i)].push_back(i);

	rep(i,1,n)if(dsu.find(i) == i)pre_solve(i);
	rep(i,1,n)if(!deg[i])pq.push(i);

	while(pq.size()){
		int u=pq.top();pq.pop();
		ans[++cur]=u;

		for(auto v:g[u]){
			deg[v]--;
			if(!deg[v])pq.push(v);
		}
	}

	rep(i,1,n)cout<<a[ans[i]]<<" ";

    return 0;
}

Submission Info

Judge Result