Submission #1645924

---

Source Code Expand

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
using namespace std;
typedef vector<int> vi;
const int N=2010;
int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}
int a[N],n;
bool v[N];
struct cmp{ bool operator () (const vi &a,const vi &b) { return a.back()<b.back(); } };
vi merge(vector<vi> p) {
	priority_queue<vi,vector<vi>,cmp>q;
	for (auto k:p) reverse(k.begin(),k.end()),q.push(k);
	vi ans,t;
	while (!q.empty()) {
		t=q.top();q.pop();
		ans.push_back(t.back());t.pop_back();
		if (!t.empty()) q.push(t);
	}
	return ans;	
}
inline vi dfs(int k) {
	v[k]=true;
	vector<vi>ans;
	for (int i=1;i<=n;i++)
		if (!v[i]&&__gcd(a[k],a[i])!=1)
			ans.push_back(dfs(i));
	vi v=merge(ans);
	v.insert(v.begin(),a[k]);
	return v;
}
int main()
{
	n=gi();
	for (int i=1;i<=n;i++) a[i]=gi();
	sort(a+1,a+1+n);
	vector<vi>ans;
	for (int i=1;i<=n;i++)
		if (!v[i])
			ans.push_back(dfs(i));
	vi v=merge(ans);
	for (auto k:v)
		printf("%d ",k);
	putchar(10);
	return 0;
}

Submission Info

Judge Result