Cod sursa(job #498166)

Utilizator iulishorIulian Popescu iulishor Data 4 noiembrie 2010 12:45:00
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include<fstream>
#define M 10005
using namespace std;
ifstream f("subsir2.in");
ofstream g("subsir2.out");
int main()
{
	int v[M],l[M],poz[M];
	int n,k,i,j,m,p,pp,nn;
	f>>n;
	nn=n;
	p=0;
	for(k=1;k<=n;++k)
	{
		f>>v[k];
		if(v[k])
		{
			i=1;
			j=p;
			pp=0;
			while(i<=j)
			{
				m=(i+j)/2;
				if(l[m]>v[k]) 
				{
					pp=m;
					j=m-1;
				}
				else 
					if(l[m]<v[k]) 
						i=m+1;
					 else 
					 {
						pp=m;
						break;
					}
			}
			if(pp==0) 
			{
				++p;
				pp=p;
			}
			l[pp]=v[k];
			poz[k]=pp;
		}
	}
	g<<p<<"\n";
	for(i=p;i>0;--i)
	{
		while(poz[n]!=i && n)
			--n;
		l[i]=v[n];
	}
	for(i=1;i<=p;i++)
		for(j=1;j<=nn;j++)
			if(l[i]==v[j])
				g<<j<<" ";
	f.close();
	g.close();
	return 0;
}