Submission #1111360

---

Source Code Expand

#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
vector<int> gr[2525],ed[2525];
bool sumi[2525];
priority_queue<int> p;
int a[2525],num[2525];
int gcd( int m, int n )
{
	int a=max(m,n),b=min(m,n);
	if(m==0) return n;if(n==0) return m;
	if(a%b==0) return b;
	return gcd(b,a-b*(a/b));
}
void cal(int v){
	//if(sumi[v]) return;
	sumi[v]=true;
	rep(i,gr[v].size()){
		int w=gr[v][i];
		if(sumi[w]) continue;
		ed[v].pb(w);
		num[w]++;
		cal(w);
	}
}
int main()
{
	int n;
	cin>>n;
	rep(i,n) cin>>a[i];
	sort(a,a+n);
	rep(i,n) rep(j,n){
		if(i!=j && gcd(a[i],a[j])>1) gr[i].pb(j),gr[j].pb(i);
	}
	memset(sumi,false,sizeof(sumi));
	memset(num,0,sizeof(num));
	rep(i,n){
		if(!sumi[i]){
			cal(i);p.push(i);
		}
	}
	vector<int> out;
	rep(i,n){
		int q=p.top();p.pop();
		out.pb(q);
		rep(j,ed[q].size()){
			int w=ed[q][j];
			num[w]--;
			if(num[w]<1) p.push(w);
		}
	}
	rep(i,n){
		cout<<a[out[i]];
		if(i<n-1) cout<<' ';else cout<<endl;
	}
}

Submission Info

Judge Result