Cod sursa(job #50227)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 7 aprilie 2007 01:12:33
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
# include <stdio.h>

const int MAXN=5000;
long int n,stack[MAXN+1],card[MAXN+1],stacklen,v[MAXN+1],sol[MAXN+1],sol2[MAXN+1],ls;
int maximum[MAXN+1];
long int nnou,lnnou;

void citire()
{
FILE *f=fopen("subsir2.in","r");
fscanf(f,"%ld",&n);
long int i;
for (i=1;i<=n;i++) fscanf(f,"%ld",&v[i]);
fclose(f);
}

long int find(long int val)
{
long int li=1,lf=stacklen,mij;
while (li<=lf)
	{
	mij=(li+lf)/2;
	if (stack[mij]>val&&(mij-1==0||stack[mij-1]<val)) return mij;
	else if (stack[mij]<val) li=mij+1;
	else lf=mij-1;
	}
return ++stacklen;
}

void calculeaza()
{
long int i,poz;lnnou=n+1;
for (i=1;i<=n;i++)
	{
	poz=find(v[i]);
	stack[poz]=v[i];
	card[i]=poz;
	if (maximum[i])
		if (lnnou>=stacklen)
			{
			lnnou=stacklen;
			nnou=i;
			}
	}
}

void pick_solution()
{
long int i;
for (i=1;i<=nnou;i++) sol[i]=1000001;
for (i=1;i<=nnou;i++)
	if (sol[card[i]]>v[i])
		{
		sol[card[i]]=v[i];
		sol2[card[i]]=i;
		}
}


void scrie()
{
FILE *g=fopen("subsir2.out","w");
fprintf(g,"%ld\n",lnnou);
long int i;
for (i=1;i<=lnnou-1;i++)
	fprintf(g,"%ld ",sol2[i]);
fprintf(g,"%ld\n",sol2[lnnou]);
fcloseall();
}

void set_maximum()
{
long int i=n-1,y=v[n];
maximum[n]=1;
while (i)
	{
	if (y<v[i])
		{
		maximum[i]=1;
		y=v[i];
		}
	i--;
	}
}

int main()
{
citire();
set_maximum();
calculeaza();
//elim_backgroundless();
pick_solution();
scrie();
return 0;
}