Cod sursa(job #915912)

Utilizator Kira96Denis Mita Kira96 Data 15 martie 2013 15:36:08
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include<fstream>
#define DIM 5001
using namespace std;
ifstream f("subsir2.in");
ofstream g("subsir2.out");
int v[DIM],s[DIM],l[DIM],k,ma,i,n,np,poz,po,maxi,viz[DIM];
int cb(int x)
{
    int st=1,dr=k,m;
    while(st<=dr)
    {
        m=(st+dr)>>1;
        if(x<s[m]&&x>s[m-1])
        return m;
        else
        if(x>s[m])
        st=m+1;
        else
        dr=m-1;
    }
    return 0;
}
void det(int k,int poz)
{
    if(k>ma)
    return ;
    int mi=999999999;
    for(i=poz;i<=n;++i)
    {
        if(l[i]==k&&v[i]<mi&&viz[i])
        {
            mi=v[i];
            np=i;
        }
    }
    g<<np<<" ";
    det(k+1,np);
}
int main ()
{
    f>>n;
    for(i=1;i<=n;++i)
    f>>v[i];
	s[0]=-999999999;
    for(i=1;i<=n;++i)
    {
        poz=cb(v[i]);
        if(poz)
        {
            s[poz]=v[i];
            l[i]=poz;
        }
        else
        {
            s[++k]=v[i];
            l[i]=k;
        }
        if(l[i]>=ma)
        {
            ma=k;
            po=i;
        }
    }
    i=n;
    maxi=ma;
    g<<ma<<"\n";
    while(i)
    {
        if(l[i]>=ma)
        {
        viz[i]=1;
		if(l[i]==ma)
        --ma;
        }
        i--;
    }
    ma=maxi;
    po=1;
    det(1,1);
    return 0;
}