Cod sursa(job #1674810)

Utilizator Theodor1000Cristea Theodor Stefan Theodor1000 Data 4 aprilie 2016 21:12:32
Problema Subsir 2 Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <cstdio>
#include <algorithm>
#include <set>

#define f first
#define s second

using namespace std;

multiset < pair <int, int> > st, sett;

int v[5010], poz[5010], to[5010];
bool start[5010];

int main ()
{
    freopen ("subsir2.in", "r", stdin);
    freopen ("subsir2.out", "w", stdout);

    int n;
    scanf ("%d", &n);

    for (int i = 1; i <= n; ++i)
        scanf ("%d", &v[i]);

    for (int i = n; i; --i)
    {
        auto it = st.lower_bound ({v[i], -1});

        if (it == st.end ()) poz[i] = 1, to[i] = -1, start[i] = true, sett.emplace (v[i], i), st.emplace_hint (st.end (), v[i], i);
        else
        {
            int val, p;
            tie (val, p) = *it;

            auto itt = sett.lower_bound ({v[i], -1});
            for (; itt != sett.end ();)
                start[(*itt).s] = false, itt = sett.erase (itt);

            sett.emplace (v[i], i);

            poz[i] = poz[p] + 1;
            to[i] = p;
            start[i] = true;

            st.emplace_hint (--it, v[i], i);
        }
    }

    int mi = 20000000, pos;
    for (int i = 1; i <= n; ++i)
        if (start[i] && (poz[i] < mi || (poz[i] == mi && v[i] < v[pos]))) mi = poz[i], pos = i;

    printf ("%d\n", mi);

    for (; pos != -1; pos = to[pos])
        printf ("%d ", pos);

    printf ("\n");

    return 0;
}