daily pastebin goal
39%
SHARE
TWEET

Untitled

Arrias Jan 18th, 2019 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define int long long
  3.  
  4. #define db(x) cout << #x <<  " = " << x << "\n";
  5.  
  6. using namespace std;
  7.  
  8. int ans[5000];
  9.  
  10. signed main() {
  11.     ios::sync_with_stdio(false);
  12.     cin.tie(0);
  13.     int n;
  14.     cin >> n;
  15.     vector <int> a(n), used(n);
  16.     for (int i = 0; i < n; ++i) {
  17.         cin >> a[i];
  18.     }
  19.     int l = 2499, r = 2501;
  20.     set <int> ls, rs, k(a.begin(), a.end());
  21.     ans[2500] = a[n - 1];
  22.     ls.insert(ans[2500]);
  23.     rs.insert(ans[2500]);
  24.     used[n - 1] = 1;
  25.     while (true) {
  26.         int left = -1;
  27.         for (int i = n - 1; i > -1; --i) {
  28.             if (used[i] == 1) continue;
  29.             int j = 0;
  30.             for (int f : ls)
  31.                 if (k.count(gcd(f, a[i])))
  32.                     ++j;
  33.             if (j == ls.size()) {
  34.                 left = 1;
  35.                 ans[l--] = a[i];
  36.                 used[i] = 1;
  37.                 break;
  38.             }
  39.             for (int f : rs)
  40.                 if (k.count(gcd(f, a[i])))
  41.                     ++j;
  42.             if (j == rs.size()) {
  43.                 left = 0;
  44.                 ans[r++] = a[i];
  45.                 used[i] = 1;
  46.                 break;
  47.             }
  48.          }
  49.         if (left == -1) break;
  50.         vector <int> ti;
  51.         if (left == 0) {
  52.             for (int z : rs)
  53.                 ti.push_back(gcd(z, ans[r - 1]));
  54.             for (int z : ti)
  55.                 rs.insert(z);
  56.         }
  57.         else {
  58.             for (int z : ls)
  59.                 ti.push_back(gcd(z, ans[l + 1]));
  60.             for (int z : ti)
  61.                 ls.insert(z);
  62.         }
  63.     }
  64.     if (r - l - 1 != n) {
  65.         cout << -1;
  66.         return 0;
  67.     }
  68.     for (int i = l + 1; i < r; ++i)
  69.         cout << ans[i] << ' ';
  70.     return 0;
  71. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top