Pagini recente » Cod sursa (job #1274451) | Cod sursa (job #493726) | Cod sursa (job #1436860) | Cod sursa (job #2980613) | Cod sursa (job #2266343)
#include <bits/stdc++.h>
using namespace std;
const int kInf = 2e9;
int main() {
ifstream cin("subsir2.in");
ofstream cout("subsir2.out");
int n; cin >> n;
vector<int> v(n);
for (int i = 0; i < n; ++i)
cin >> v[i];
vector<pair<int, int>> dp(n);
dp[0] = {0, -1};
vector<int> stk = {0};
for (int i = 1; i < n; ++i) {
dp[i].first = kInf;
while (stk.size()) {
int j = stk.back();
if (v[j] > v[i]) break;
dp[i] = min(dp[i], make_pair(dp[j].first, j));
stk.pop_back();
}
dp[i].first += 1;
stk.push_back(i);
}
pair<int, int> best = {kInf, -1};
for (auto x : stk)
best = min(best, make_pair(dp[x].first, x));
vector<int> ans;
for (int pos = best.second; pos != -1; pos = dp[pos].second)
ans.push_back(pos);
reverse(ans.begin(), ans.end());
cout << ans.size() << endl;
for (auto x : ans)
cout << x + 1 << " ";
cout << endl;
return 0;
}