Cod sursa(job #950422)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 16 mai 2013 19:48:07
Problema Subsir 2 Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 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;

int main ()
{
    fin>>n;
    for (i=1;i<=n;i++) fin>>v[i];
    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 for (j=1;j<=n;j++)
        {
            if (v[i]<s[j]) {s[j]=v[i]; l=j; ind[j]=i; break;}
        }
        /*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++;
        s[ls]=v[i]; l=ls;
        ind[l]=i;
        }*/
    }
    fout<<l<<"\n";
    for (i=1;i<=l;i++) fout<<ind[i]<<" ";
}