Cod sursa(job #915634)

Utilizator Kira96Denis Mita Kira96 Data 15 martie 2013 10:31:33
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 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)
		{
			mi=v[i];
			np=i;
		}
	}
	g<<np<<" ";
	det(k+1,np);
}
int main ()
{
	f>>n;
	for(i=1;i<=n;++i)
	f>>v[i];
	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(k>ma)
		{
			ma=k;
			po=i;
		}
	}
	i=po;
	maxi=ma;
	g<<ma<<"\n";
	while(ma)
	{
		if(v[i]>=ma)
		{
		viz[i]=1;
		--ma;
		}
		i--;
	}
	ma=maxi;
	po=1;
	det(1,1);
	return 0;
}