The_Law

Untitled

Jan 30th, 2017
237
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.45 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int INF = 1e4;
  6.  
  7. vector<int> arr;
  8. vector<int> numb;
  9. vector<int> d;
  10. vector<int> p;
  11. vector<int> ans;
  12.  
  13. int main()
  14. {
  15. //    freopen("D.in", "r", stdin);
  16.     freopen("input.txt", "r", stdin);
  17.     freopen("output.txt", "w", stdout);
  18.  
  19.     int n;
  20.     cin >> n;
  21.  
  22.     arr.resize(n);
  23.     d.resize(n, 0);
  24.     numb.resize(INF + 1, -1);
  25.     p.resize(n, -1);
  26.  
  27.     for (int i = 0; i < n; ++i)
  28.     {
  29.         cin >> arr[i];
  30.  
  31.         int currmax = 0;
  32.  
  33.         for (int j = 1; j * j < arr[i] + 1; ++j)
  34.             if (arr[i] % j == 0)
  35.             {
  36.                 if (numb[j] >= 0 && currmax < d[numb[j]])
  37.                 {
  38.                     currmax = d[numb[j]];
  39.                     p[i] = numb[j];
  40.                 }
  41.  
  42.                 if (numb[arr[i] / j] >= 0 && currmax < d[numb[arr[i] / j]])
  43.                 {
  44.                     currmax = d[numb[arr[i] / j]];
  45.                     p[i] = numb[arr[i] / j];
  46.                 }
  47.             }
  48.  
  49.         d[i] = currmax + 1;
  50.         numb[arr[i]] = i;
  51.     }
  52.  
  53.     int maxel = -INF;
  54.     int it;
  55.  
  56.     for (int i = 0; i < n; ++i)
  57.         if (d[i] > maxel)
  58.         {
  59.             maxel = d[i];
  60.             it = i;
  61.         }
  62.  
  63.     while (it >= 0)
  64.     {
  65.         ans.push_back(it);
  66.         it = p[it];
  67.     }
  68.  
  69.     cout << ans.size() << endl;
  70.  
  71.     for (int i = ans.size() - 1; i >= 0; --i)
  72.         cout << ans[i] + 1 << ' ';
  73.  
  74.     return 0;
  75. }
Advertisement
Add Comment
Please, Sign In to add comment