Submission #1844401
Source Code Expand
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#define rep(i, a, b) for (int i = (a), _ = (b); i <= _; ++ i)
#define per(i, a, b) for (int i = (a), _ = (b); i >= _; -- i)
#define For(i, a, b) for (int i = (a), _ = (b); i < _; ++ i)
#define fore(e, u, v) for (int p = e(u), v = e[p].y; p; v = e[p = e[p].nxt].y)
#define ri rd<int>
using namespace std;
const int maxN = 2e3 + 7;
template<class T> inline T rd() {
bool f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = 0;
T x = 0; for (; isdigit(c); c = getchar()) x = x * 10 + c - 48; return f ? x : -x;
}
inline int gcd(int x, int y) { while (y) swap(x %= y, y); return x; }
int n, a[maxN];
bool vis[maxN];
int deg[maxN];
int ans[maxN], tt;
struct vec {
static const int maxE = maxN * maxN;
int g[maxN], te;
struct edge {int y, nxt;} e[maxE << 1];
inline void push(int x, int y) { e[++te] = (edge){y, g[x]}; g[x] = te; }
inline void link(int x, int y) { push(x, y), push(y, x); }
inline int& operator () (int x) { return g[x]; }
inline edge& operator [] (int x) { return e[x]; }
}e, G;
int bac[maxN];
void dfs(int x) {
vis[x] = 1;
fore (e, x, y) if (!vis[y]) { // from small to big
dfs(y);
G.push(x, y);
++ deg[y];
}
}
void topu() {
static priority_queue<int, vector<int>, less<int> > q;
q.push(0);
while (!q.empty()) {
int x = q.top(); q.pop();
if (x) ans[++tt] = a[x];
fore (G, x, y) if (-- deg[y] == 0) q.push(y);
}
rep (i, 1, tt) printf("%d%c", ans[i], " \n"[i == tt]);
}
int main() {
n = ri(); rep (i, 1, n) a[i] = ri();
sort(a+1, a+n+1);
rep (i, 1, n) per (j, n, 1) if (gcd(a[i], a[j]) != 1) e.push(i, j);
per (i, n, 1) e.link(0, i);
dfs(0);
topu();
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Rearranging |
User |
acha |
Language |
C++14 (GCC 5.4.1) |
Score |
1600 |
Code Size |
1863 Byte |
Status |
AC |
Exec Time |
496 ms |
Memory |
22912 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1600 / 1600 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample1.txt, sample2.txt |
All |
sample1.txt, sample2.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in3.txt, in30.txt, in31.txt, in32.txt, in33.txt, in34.txt, in35.txt, in36.txt, in37.txt, in38.txt, in39.txt, in4.txt, in40.txt, in41.txt, in42.txt, in43.txt, in44.txt, in45.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt |
Case Name |
Status |
Exec Time |
Memory |
in1.txt |
AC |
495 ms |
14720 KB |
in10.txt |
AC |
494 ms |
14720 KB |
in11.txt |
AC |
422 ms |
4480 KB |
in12.txt |
AC |
425 ms |
4480 KB |
in13.txt |
AC |
421 ms |
4480 KB |
in14.txt |
AC |
424 ms |
4480 KB |
in15.txt |
AC |
423 ms |
4480 KB |
in16.txt |
AC |
425 ms |
22912 KB |
in17.txt |
AC |
426 ms |
22912 KB |
in18.txt |
AC |
425 ms |
22912 KB |
in19.txt |
AC |
426 ms |
22912 KB |
in2.txt |
AC |
494 ms |
14720 KB |
in20.txt |
AC |
425 ms |
22912 KB |
in21.txt |
AC |
320 ms |
2304 KB |
in22.txt |
AC |
321 ms |
2304 KB |
in23.txt |
AC |
323 ms |
2304 KB |
in24.txt |
AC |
321 ms |
2304 KB |
in25.txt |
AC |
321 ms |
2304 KB |
in26.txt |
AC |
423 ms |
4480 KB |
in27.txt |
AC |
424 ms |
4480 KB |
in28.txt |
AC |
421 ms |
4480 KB |
in29.txt |
AC |
425 ms |
4480 KB |
in3.txt |
AC |
494 ms |
14720 KB |
in30.txt |
AC |
424 ms |
4480 KB |
in31.txt |
AC |
2 ms |
2304 KB |
in32.txt |
AC |
2 ms |
2304 KB |
in33.txt |
AC |
2 ms |
2304 KB |
in34.txt |
AC |
378 ms |
2304 KB |
in35.txt |
AC |
377 ms |
2304 KB |
in36.txt |
AC |
444 ms |
6528 KB |
in37.txt |
AC |
443 ms |
6528 KB |
in38.txt |
AC |
445 ms |
6528 KB |
in39.txt |
AC |
446 ms |
6528 KB |
in4.txt |
AC |
496 ms |
14720 KB |
in40.txt |
AC |
444 ms |
6528 KB |
in41.txt |
AC |
444 ms |
6528 KB |
in42.txt |
AC |
446 ms |
6528 KB |
in43.txt |
AC |
443 ms |
6528 KB |
in44.txt |
AC |
445 ms |
6528 KB |
in45.txt |
AC |
446 ms |
6528 KB |
in5.txt |
AC |
493 ms |
14720 KB |
in6.txt |
AC |
495 ms |
14720 KB |
in7.txt |
AC |
494 ms |
14720 KB |
in8.txt |
AC |
495 ms |
14720 KB |
in9.txt |
AC |
495 ms |
14720 KB |
sample1.txt |
AC |
2 ms |
2304 KB |
sample2.txt |
AC |
2 ms |
2304 KB |