Cod sursa(job #1691254)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 17 aprilie 2016 17:37:15
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <cstdio>
using namespace std;
FILE *f=fopen("subsir2.in","r");
FILE *g=fopen("subsir2.out","w");
int M[5005],lmax;
int P[5005],i;
int V[5005],rez[5005];
int N,st,dr,last,mid,minim=5005,j;
bool used[5005];
int main()
{
    fscanf(f,"%d",&N);
    for(i=1;i<=N;i++)
    {
        fscanf(f,"%d",&V[i]);
        st=1;
        dr=lmax;
        last=0;
        while(st<=dr)
        {
            mid=(st+dr)/2;
            if(V[M[mid]]<=V[i])
            {
                last=mid;
                st=mid+1;
            }
            else
                dr=mid-1;
        }
        P[i]=M[last];
        if(last+1>lmax)
        {
            lmax++;
            M[lmax]=i;
        }
        else
        {
            if(V[i]<V[M[last+1]])
            {
                M[last+1]=i;
            }
        }
    }
    for(i=lmax;i>0;i--)
    {
        if(!used[M[i]])
        {
            minim=i;
            j=M[i];
            while(j!=0)
            {
                used[j]=1;
                j=P[j];
            }
        }
    }
    fprintf(g,"%d\n",minim);
    j=M[minim];
    while(j)
    {
        rez[++rez[0]]=j;
        j=P[j];
    }
    for(i=rez[0];i>0;i--)
        fprintf(g,"%d ",rez[i]);
    fclose(f);
    fclose(g);
    return 0;
}