fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX = 1e7 + 1;
  5.  
  6. vector<int> spf(MAX);
  7.  
  8. void sieve() {
  9.     spf[1] = 1;
  10.     for (int i = 2; i < MAX; ++i) {
  11.         if (spf[i] == 0) {
  12.             spf[i] = i;
  13.             for (int j = i * 2; j < MAX; j += i) {
  14.                 if (spf[j] == 0) spf[j] = i;
  15.             }
  16.         }
  17.     }
  18. }
  19.  
  20. vector<int> factorize(int x) {
  21.     vector<int> res;
  22.     if (x == 1) return res;
  23.     while (x != 1) {
  24.         int p = spf[x];
  25.         res.push_back(p);
  26.         while (x % p == 0) x /= p;
  27.     }
  28.     return res;
  29. }
  30.  
  31. struct DSU {
  32.     vector<int> parent, rank, parity;
  33.  
  34.     DSU(int n) {
  35.         parent.resize(n);
  36.         rank.resize(n, 0);
  37.         parity.resize(n, 0);
  38.         for (int i = 0; i < n; ++i) parent[i] = i;
  39.     }
  40.  
  41.     pair<int, int> find(int u) {
  42.         if (parent[u] != u) {
  43.             int p = parent[u];
  44.             auto [root, par] = find(p);
  45.             parent[u] = root;
  46.             parity[u] ^= par;
  47.         }
  48.         return {parent[u], parity[u]};
  49.     }
  50.  
  51.     bool unite(int u, int v) {
  52.         auto [root_u, par_u] = find(u);
  53.         auto [root_v, par_v] = find(v);
  54.  
  55.         if (root_u == root_v) {
  56.             return (par_u != par_v);
  57.         }
  58.  
  59.         if (rank[root_u] < rank[root_v]) {
  60.             swap(root_u, root_v);
  61.             swap(par_u, par_v);
  62.         }
  63.  
  64.         parent[root_v] = root_u;
  65.         parity[root_v] = (par_u == par_v) ? 1 : 0;
  66.         if (rank[root_u] == rank[root_v]) ++rank[root_u];
  67.         return true;
  68.     }
  69. };
  70.  
  71. int main() {
  72.     ios_base::sync_with_stdio(false);
  73.     cin.tie(nullptr);
  74.  
  75.     sieve();
  76.  
  77.     int n;
  78.     cin >> n;
  79.     vector<int> a(n);
  80.     for (auto &x : a) cin >> x;
  81.  
  82.     map<int, vector<int>> prime_to_indices;
  83.  
  84.     for (int i = 0; i < n; ++i) {
  85.         int x = a[i];
  86.         auto primes = factorize(x);
  87.         for (int p : primes) {
  88.             prime_to_indices[p].push_back(i);
  89.         }
  90.     }
  91.  
  92.     for (auto &[p, indices] : prime_to_indices) {
  93.         if (indices.size() > 2) {
  94.             cout << -1 << endl;
  95.             return 0;
  96.         }
  97.     }
  98.  
  99.     DSU dsu(n);
  100.  
  101.     for (auto &[p, indices] : prime_to_indices) {
  102.         if (indices.size() == 2) {
  103.             int u = indices[0];
  104.             int v = indices[1];
  105.             if (!dsu.unite(u, v)) {
  106.                 cout << -1 << endl;
  107.                 return 0;
  108.             }
  109.         }
  110.     }
  111.  
  112.     vector<int> group(n, 1);
  113.     for (int i = 0; i < n; ++i) {
  114.         auto [root, par] = dsu.find(i);
  115.         if (par == 1) {
  116.             group[i] = 2;
  117.         }
  118.     }
  119.  
  120.     for (int g : group) {
  121.         cout << g << " ";
  122.     }
  123.     cout << endl;
  124.  
  125.     return 0;
  126. }
Success #stdin #stdout 0.19s 42320KB
comments (?)
stdin
copy 
5
10 30 21 7 1
1 2 1 2 2
1 2 1 2 1
2 1 2 1 1
2 1 2 1 2
stdout
copy 
1 2 1 2 1
https://ideone.com/87Zu5R
language:
C++ (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!