Submission #1096333

---

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];

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

	queue<int> Qa, Qb;
	// place [0, iic] first
//	printf("chk %d\n", A[iic]);
	for (int i = 0; i <= iic; ++i) if (!used[i] && isok[i]) {
		Qa.push(i);
		vis[i] = true;
	}
	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;
				if (i <= iic) Qa.push(i);
				else Qa.push(i);
			}
		}
	}
	/*
	while (!Qb.empty()) {
		int v = Qb.front(); Qb.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;
				if (i <= iic) {
					puts("><");
					exit(0);
				} else Qb.push(i);
			}
		}
	}
	*/
	for (int i = 0; i < N; ++i) if (!used[i] && !vis[i]) return false;
	return true;
}

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) {
		vector<int> cand;
		for (int j = 0; j < N; ++j) if (!used[j]) cand.push_back(j);

		int left = 0, right = cand.size() - 1;
		while (left < right) {
			int mid = (left + right) / 2;
			if (chk(cand[mid])) {
				right = mid;
			} else {
				left = mid + 1;
			}
		}
		int v = A[cand[left]];
		ans.push_back(v);
	//	printf("%d\n", v);
		used[cand[left]] = 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:80:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
./Main.cpp:82:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", A + i);
                     ^

Judge Result