Cod sursa(job #950442)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 16 mai 2013 20:42:15
Problema Subsir 2 Scor 46
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
using namespace std;
ifstream fin ("subsir2.in");
ofstream fout ("subsir2.out");

int s[5001],l,v[5001],n,i,ls,ld,m,ind[5001],j,succ[5001];

int main ()
{
    fin>>n;
    for (i=1;i<=n;i++) fin>>v[i];
    succ[n]=0;
    for (i=n-1;i>=1;i--)
    {
        for (j=i+1;j<=n;j++)
        {
            if (v[i]<=v[j]) {succ[i]=succ[j]+1; break;}
        }
    }
    s[1]=v[1]; l=1; ind[1]=1;
    for (i=2;i<=n;i++)
    {
        if (v[i]>=s[l]) {s[++l]=v[i]; ind[l]=i;}
        else
        {
            ls=1; ld=l;
            while (ls<ld)
            {
                m=(ls+ld)/2;
                if (v[i]>s[m]) ls=m+1;
                else ld=m-1;
            }
        while (s[ls]<=v[i]) ls++;
        if (succ[i]<succ[ind[ls]])
        {
            s[ls]=v[i];
            l=ls;
            ind[l]=i;
        }
        }
    }
    fout<<l<<"\n";
    for (i=1;i<=l;i++) fout<<ind[i]<<" ";
}