Submission #1096410

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int gcd(int a, int b)
{
	while (b) {
		int t = a % b;
		a = b;
		b = t;
	}
	return a;
}

int N, A[2020];
vector<int> dv[2020];
vector<int> rdiv[50505];
int RC;

bool isok[2020], used[2020];
bool rdivvis[50505];
bool vis[2020];

int chk()
{
	for (int i = 0; i < N; ++i) vis[i] = false;
	for (int i = 0; i < RC; ++i) rdivvis[i] = false;

	queue<int> Qa;
	int top = 0;
	int ret = -1;

	for (;;) {
		while (top < N) {
			if (!used[top] && isok[top] && !vis[top]) {
				Qa.push(top);
				vis[top] = true;
				ret = top;
				break;
			}
			++top;
		}
		if (top == N) break;
		while (!Qa.empty()) {
			int v = Qa.front(); Qa.pop();
			for (int p : dv[v]) if (!rdivvis[p]) {
				rdivvis[p] = true;
				for (int i : rdiv[p]) if (!used[i] && !vis[i]) {
					vis[i] = true;
					Qa.push(i);
				}
			}
		}
	}
	return ret;
}

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		scanf("%d", A + i);
	}
	sort(A, A + N);
	for (int i = 0; i < N; ++i) {
		int v = A[i];
		for (int j = 2; j * j <= v; ++j) {
			if (v % j == 0) {
				dv[i].push_back(j);
				while (v % j == 0) v /= j;
			}
		}
		if (v > 1) dv[i].push_back(v);
	}
	vector<int> alldv;
	for (int i = 0; i < N; ++i) {
		for (int p : dv[i]) alldv.push_back(p);
	}
	sort(alldv.begin(), alldv.end());
	alldv.erase(unique(alldv.begin(), alldv.end()), alldv.end());
	for (int i = 0; i < N; ++i) {
		for (int &p : dv[i]) {
			p = lower_bound(alldv.begin(), alldv.end(), p) - alldv.begin();
			rdiv[p].push_back(i);
		}
	}
	RC = alldv.size();

	for (int i = 0; i < N; ++i) {
		isok[i] = true;
		used[i] = false;
	}

	vector<int> ans;
	for (int i = 0; i < N; ++i) {
		int id = chk();
		int v = A[id];
		ans.push_back(v);
	//	printf("%d\n", v);
		used[id] = true;
		for (int j = 0; j < N; ++j) {
			if (A[j] > v) {
				isok[j] = false;
			}
			if (gcd(A[j], v) != 1) {
				isok[j] = true;
			}
		}
	}

	for (int i = 0; i < N; ++i) printf("%d%c", ans[i], i == N - 1 ? '\n' : ' ');

	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:72:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
./Main.cpp:74:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", A + i);
                     ^

Judge Result