Cod sursa(job #2214637)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 19 iunie 2018 15:28:53
Problema Subsir 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back

using namespace std;

ifstream f ("subsir2.in");
ofstream g ("subsir2.out");

int main() {
    int n;
    f >> n;
    vector <int> v(n), len(n, 0), capat(n, 0);
    vector <bool> isStart(n, true);
    for (int i = 0; i < n; ++i) f >> v[i];
    int ans = 1 << 30;
    int pos = 0;
    for (int i = n - 1; i >= 0; --i) {
        int minn = v[i + 1];
        len[i] = 1 << 30;
        for (int j = i + 1; j < n; ++j) {
            if (v[i] <= v[j]) {
                if (v[j] < minn) {
                    minn = v[j];
                    if (len[j] + 1 < len[i]) {
                        len[i] = 1 + len[j];
                        capat[i] = j;
                    }
                }
                isStart[j] = false;
            }
        }
        if (len[i] == 1 << 30 && capat[i] == 0) {
            len[i] = 1; capat[i] = i;
        }
    }
    for (int i = 0; i < n; ++i) {
        if (isStart[i]) {
            if (ans > len[i]) {
                ans = len[i];
                pos = i;
            }
        }
    }
    g << ans << '\n' << pos + 1 << ' ';
    function <void(int)> reconstr = [&](int pos) {
        if (capat[pos] == pos) return;
        g << capat[pos] + 1 << ' ';
        reconstr(capat[pos]);
    };
    reconstr (pos);

    f.close();
    g.close();
    return 0;
}