Cod sursa(job #2266343)

Utilizator retrogradLucian Bicsi retrograd Data 22 octombrie 2018 16:33:09
Problema Subsir 2 Scor 36
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#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;
}