Cod sursa(job #1500708)

Utilizator refugiatBoni Daniel Stefan refugiat Data 12 octombrie 2015 16:45:11
Problema Subsir 2 Scor 48
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include<iostream>
#include<fstream>
#include<bitset>
using namespace std;
const int NMAX=5005;
const int inf=10000000;
int v[NMAX],lg[NMAX],suc[NMAX];
bitset<NMAX> extins;
int main()
{
    ifstream si;
    si.open("subsir2.in");
    ofstream so;
    so.open("subsir2.out");
    int n;
    si>>n;
    int i;
    for(i=1;i<=n;++i)
        si>>v[i];
    int j,k;
    for(i=n;i>0;--i)
    {
        k=inf;
        lg[i]=inf;
        for(j=i+1;j<=n;++j)
        {
            if(k>v[j]&&v[i]<v[j])
            {
                extins[j]=1;
                k=v[j];
                if(lg[j]+1<lg[i])
                {
                    lg[i]=lg[j]+1;
                    suc[i]=j;
                }
                else
                    if(lg[j]+1==lg[i])
                        suc[i]=j;
            }
        }
        if(k==inf)
            lg[i]=1;
    }
    /*for(i=1;i<=n;++i)
        cout<<v[i]<<' ';
    cout<<'\n';
    for(i=1;i<=n;++i)
        cout<<lg[i]<<' ';
    cout<<'\n';
    for(i=1;i<=n;++i)
        cout<<suc[i]<<' ';
    cout<<'\n';
    for(i=1;i<=n;++i)
        cout<<extins[i]<<' ';
    cout<<'\n';*/
    int minn=inf+3,poz=0;
    for(i=1;i<=n;i++)
    {
        if(!extins[i])
        {
            if(minn>lg[i])
            {
                minn=lg[i];
                poz=i;
            }
            else
            {
                if(minn==lg[i])
                {
                    j=i;
                    k=poz;
                    while(j&&v[j]==v[k])
                    {
                        j=suc[j];
                        k=suc[k];
                    }
                    if(!j&&v[j]<v[k])
                        poz=i;
                }
            }
        }
    }
    so<<minn<<'\n';
    while(poz)
    {
        so<<poz<<' ';
        poz=suc[poz];
    }
    so<<'\n';
    return 0;
}