Cod sursa(job #182595)

Utilizator hulparuadrianhulparu adrian hulparuadrian Data 21 aprilie 2008 09:07:41
Problema Subsir crescator maximal Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include<stdio.h>
#define ooo 100001
#define cucu 0
int n,len;
int v[ooo],p[ooo],q[ooo];
void DataRead()
{
freopen("scmax.in","r",stdin);
scanf("%i",&n);
for(int i=1;i<=n;i++)
	scanf("%i",&v[i]);
fclose(stdin);
}

int insert(int k,int l,int h)
{
int m=(l+h)/2;
if (l==h)
	{if (h>len) q[++len+1]=cucu;
	q[l]=k;
	return l;}
		 else if (k<q[m]) return insert(k,l,m);
		 else return insert(k,m+1,h);
}

void build()
{
len=0;q[1]=cucu;
for(int i=1;i<=n;i++)
	p[i]=insert(v[i],1,len+1);
}


void WriteSolution()
{
int i;
freopen("scmax.out","w",stdout);
int lungime=len;
for(i=2;i<=len;i++)
	if (q[i]==q[i-1]) {lungime--;}
printf("%i\n",lungime);
printf("%i ",q[1]);
for(i=2;i<=len;i++)
      {
	if (q[i]!=q[i-1]) {printf("%i ",q[i]);}
      }

fclose(stdout);
}

int main()
{
DataRead();
build();
int k=n;
for(int i=len;i;i--)
	{while(p[k]!=i) k--;
	q[i]=v[k];}
WriteSolution();
return 0;
}