Cod sursa(job #2129074)

Utilizator papinub2Papa Valentin papinub2 Data 12 februarie 2018 14:33:46
Problema Subsir 2 Scor 58
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int Nmax = 5005;

int compara (int&a, int&b, vector<int>&v, vector<int>&poz)
{
    int x = a;
    int y = b;

    while (x != -1)
    {
        if (x > y)
            return a;

        if (y > x)
            return b;

        x = v[poz[x]];
        y = v[poz[y]];
    }

    return a;
}

int main()
{
    int n, a, b, start, minim = Nmax + 5;
    vector<int> v(Nmax);
    vector<int> poz(Nmax);
    vector<int> urm(Nmax);
    vector<int> best(Nmax);

    in >> n;

    for (int i = 1; i <= n; i++)
    {
        in >> v[i];
        best[i] = 1;
    }
    poz[n] = -1;

    for (int i = n - 1; i >= 1; i--)
    {
        poz[i] = -1;
        for (int j = i + 1; j <= n; j++)
            if (v[i] < v[j])
            {
                if (best[i] < best[j] + 1)
                {
                    best[i] = best[j] + 1;
                    poz[i] = j;
                }

                else

                if (best[i] == best[j] + 1)
                {
                    if (v[j] < v[poz[i]])
                        poz[i] = j;
                }

                urm[j] = i;
            }
    }

    for (int i = 1; i <= n; i++)
    {
        if (urm[i] == 0 && best[i] == minim)
        {
            b = i;
            start = compara(a, b, v, poz);
        }

        if (urm[i] == 0 && best[i] < minim)
        {
            minim = best[i];
            a = i;
            start = i;
        }
    }

    out << best[start] << '\n';
    out << start << ' ';

    while (poz[start] != -1)
    {
        out << poz[start] << ' ';
        start = poz[start];
    }

    return 0;
}