fork(3) download
copy 
  1. //84104971101048411497 - Can you guess what does this mean?
  2. using namespace std;
  3. #include <bits/stdc++.h>
  4. #define mapii map<int, int>
  5. #define debug(a) cout << #a << ": " << a << endl
  6. #define debuga1(a, l, r) fto(i, l, r) cout << a[i] << " "; cout << endl
  7. #define fdto(i, r, l) for(int i = (r); i >= (l); --i)
  8. #define fto(i, l, r) for(int i = (l); i <= (r); ++i)
  9. #define ftoa(i, l, r, a) for(int i = (l); i <= (r); i += a)
  10. #define forit(it, var) for(__typeof(var.begin()) it = var.begin(); it != var.end(); it++)
  11. #define forrit(rit, var) for(__typeof(var.rbegin()) rit = var.rbegin(); rit != var.rend(); rit++)
  12. #define ii pair<int, int>
  13. #define iii pair<int, ii>
  14. #define ff first
  15. #define ss second
  16. #define mp make_pair
  17. #define pb push_back
  18. #define ll long long
  19. #define sizeX 10000005
  20. #define next abcxyz
  21. #define sz(a) (int)(a.size())
  22.  
  23. template <class T>
  24. T min(T a, T b, T c) {
  25.     return min(a, min(b, c));
  26. }
  27.  
  28. template <class T>
  29. T max(T a, T b, T c) {
  30.     return max(a, max(b, c));
  31. }
  32.  
  33. template <class T>
  34. void read(vector<T> &v) {
  35.     T x;
  36.     cin >> x;
  37.     v.pb(x);
  38. }
  39.  
  40. struct edge {
  41.     int u, v, c;
  42.     edge() {}
  43.     edge(int u, int v, int c): u(u), v(v), c(c) {}
  44.     bool inline operator < (const edge &o) const {
  45.         return c < o.c;
  46.     }
  47. };
  48.  
  49. int n, next[sizeX];
  50. bool avail[sizeX];
  51. vector<int> a;
  52. vector<edge> e;
  53.  
  54. class UFDS {
  55. private: int n; vector<int> pset;
  56. public:
  57.     UFDS(int n) {
  58.         pset.resize(n);
  59.         fto(i, 0, n-1) pset[i] = i;
  60.     }
  61.     int findSet(int u) {
  62.         return (pset[u] == u) ? u : pset[u] = findSet(pset[u]);
  63.     }
  64.     bool unionSet(int u, int v) {
  65.         int p = findSet(u), q = findSet(v);
  66.         if (p == q) return false;
  67.         pset[p] = q;
  68.         return true;
  69.     }
  70. };
  71.  
  72. int main () {
  73.     #ifndef ONLINE_JUDGE
  74.         freopen("input.txt", "r", stdin);
  75.         //freopen("output.txt", "w", stdout);
  76.     #endif // ONLINE_JUDGE
  77.  
  78.     scanf("%d", &n);
  79.     int maxX = 0;
  80.     fto(i, 0, n-1) {
  81.         int x; scanf("%d", &x);
  82.         avail[x] = true;
  83.         maxX = max(maxX, x);
  84.     }
  85.  
  86.     next[maxX+1] = -1;
  87.     fdto(x, maxX, 1) {
  88.         if (avail[x]) {
  89.             next[x] = sz(a);
  90.             a.pb(x);
  91.         } else next[x] = next[x+1];
  92.     }
  93.  
  94.     memset(avail, false, sizeof avail);
  95.     fto(i, 0, sz(a)-1) {
  96.         vector<int> save;
  97.         ftoa(k, a[i], maxX, a[i]) {
  98.             int j = next[k + (k == a[i])];
  99.             if (j >= 0 && !avail[j]) {
  100.                 e.pb(edge(i, j, a[j]%a[i]));
  101.                 avail[j] = true; save.pb(j);
  102.             }
  103.         }
  104.         forit(it, save) avail[*it] = false;
  105.     }
  106.  
  107.     sort(e.begin(), e.end());
  108.  
  109.     UFDS s(a.size());
  110.     int ans = 0;
  111.     forit(it, e) {
  112.         if (s.unionSet(it->u, it->v)) ans += it->c;
  113.     }
  114.  
  115.     printf("%d", ans);
  116.  
  117.     return 0;
  118. }
  119.  
  120.  
Success #stdin #stdout 0s 52304KB
comments (?)
stdin
copy 
4
2
6
3
11
stdout
copy 
1
https://ideone.com/s2ntSW
COCI 2017 R6 - Sirni
language:
C++14 (gcc 8.3)
created:
7 years 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!