SHARE
TWEET

Untitled

a guest Jan 17th, 2020 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <map>
  5. using namespace std;
  6.  
  7. #define ll long long
  8.  
  9. ll n;
  10.  
  11. using namespace std;
  12.  
  13. const ll M = (ll)(2e6+1);
  14. ll a[M];
  15. map<ll, ll> m;
  16. ll b[M];
  17.  
  18. bool cmp(vector<ll> v1, vector<ll> v2) {
  19.     if (v1[0] == v2[0])
  20.         return v1[1] < v2[1];
  21.     return v1[0] < v2[0];
  22. }
  23.  
  24. int main()
  25. {
  26.     //freopen("equal.in", "r", stdin);
  27.     //freopen("equal.out", "w", stdout);
  28.    
  29.     cin >> n;
  30.     for (ll i = 0; i < n; i++) {
  31.         cin >> a[i];
  32.         m[a[i]] += 1;
  33.     }
  34.  
  35.     vector<vector<ll> > v;
  36.     vector<vector<ll> > v_child;
  37.     for (auto p: m) {
  38.         ll val = p.first;
  39.         bool mult = false;
  40.         for (ll j = val*2; j <= (ll)(1e6); j += val) {
  41.             if (b[j]) {
  42.                 mult = true;
  43.             }
  44.         }
  45.  
  46.         if (mult) v_child.push_back({p.second, p.first});
  47.  
  48.         v.push_back({p.second, p.first});
  49.     }
  50.  
  51.     sort(v.begin(), v.end(), cmp);
  52.     sort(v_child.begin(), v_child.end(), cmp);
  53.  
  54.     vector<ll> ans(n+1);
  55.  
  56.     ll idx = 0;
  57.     ll elim = 0;
  58.     ll bins = v_child.size();
  59.     for (ll k = 0; k <= n; k++) {
  60.         if (v_child[idx][0] == 0) {
  61.             elim++;
  62.             idx++;
  63.         }
  64.  
  65.         ans[k] = bins - elim;
  66.         if (idx >= v_child.size()) break;
  67.         if (k != n) v[idx][0]--;
  68.     }
  69.  
  70.     idx = 0;
  71.     elim = 0;
  72.     bins = v.size();
  73.     for (ll k = 0; k <= n; k++) {
  74.         if (v[idx][0] == 0) {
  75.             elim++;
  76.             idx++;
  77.         }
  78.  
  79.         ans[k] = min(ans[k], bins - elim + 1);
  80.         if (idx >= v.size()) break;
  81.         v[idx][0]--;
  82.     }
  83.  
  84.  
  85.     for (ll i = 0; i <= n; i++)
  86.         cout << ans[i] << " ";
  87.     cout << endl;
  88.  
  89.     return 0;
  90.     for (auto vv: v) {
  91.         for (auto x : vv) {
  92.             cout << x << " " ;     
  93.         }
  94.         cout << endl;
  95.     }
  96.  
  97. }
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