Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int INF = 1e4;
- vector<int> arr;
- vector<int> numb;
- vector<int> d;
- vector<int> p;
- vector<int> ans;
- int main()
- {
- // freopen("D.in", "r", stdin);
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- int n;
- cin >> n;
- arr.resize(n);
- d.resize(n, 0);
- numb.resize(INF + 1, -1);
- p.resize(n, -1);
- for (int i = 0; i < n; ++i)
- {
- cin >> arr[i];
- int currmax = 0;
- for (int j = 1; j * j < arr[i] + 1; ++j)
- if (arr[i] % j == 0)
- {
- if (numb[j] >= 0 && currmax < d[numb[j]])
- {
- currmax = d[numb[j]];
- p[i] = numb[j];
- }
- if (numb[arr[i] / j] >= 0 && currmax < d[numb[arr[i] / j]])
- {
- currmax = d[numb[arr[i] / j]];
- p[i] = numb[arr[i] / j];
- }
- }
- d[i] = currmax + 1;
- numb[arr[i]] = i;
- }
- int maxel = -INF;
- int it;
- for (int i = 0; i < n; ++i)
- if (d[i] > maxel)
- {
- maxel = d[i];
- it = i;
- }
- while (it >= 0)
- {
- ans.push_back(it);
- it = p[it];
- }
- cout << ans.size() << endl;
- for (int i = ans.size() - 1; i >= 0; --i)
- cout << ans[i] + 1 << ' ';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment