Cod sursa(job #203729)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 19 august 2008 01:41:57
Problema Subsir 2 Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <cstdio>
#define min(x,y) x<y ? x:y

#define IN  "subsir2.in"
#define OUT "subsir2.out"
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define N_MAX 1<<13

int N;
int A[N_MAX],T[N_MAX],V[N_MAX];
char ch[1<<20];

int main()
{
	int semn;
	freopen(IN, "r",stdin);
	freopen(OUT, "w",stdout);
	scanf("%d\n", &N);
	gets(ch);
	V[0] = 1;
	for(int i=0;ch[i] != '\0' && ch[i] !='\n';++i)
	{
		if(ch[i] == '-')
			++i,semn = V[0];
		V[ V[0] ] = V[ V[0] ] * 10 + ch[i] - '0';
		if(ch[i+1] == ' ')
		{
			if(semn == V[0])
				V[ V[0] ] *= -1;
			++i,++V[0];
		}	
	}

	int best,minim;
	A[0] = 1<<21;
	V[0] = 1<<21;
	bool ok;
	for(int i=N;i>=1;--i)
	{
		best = 0;
		ok = 0;minim = 0;
		FOR(j,i+1,N)
			if(V[j] >= V[i])
			{
				if( (A[j] < A[best] || (A[j] == A[best] && V[j] < V[best] ) ) && V[j] < V[minim])
				{
					best = j;
					ok=1;
				}
				if(V[j] < V[minim])
					minim = j;
			}	
		if(ok)
			A[i] = A[best] + 1,
			T[i] = best;
		else
			A[i] = 1,
			T[i] = i;
	}	
	
	best = 0;
	minim = 1<<21;
		
	FOR(i,1,N)
	{
		if( (A[i] < A[best] ||  (A[i] == A[best] && V[i] < V[best]) ) && V[i] < minim)
			best = i;
		minim = min(minim,V[i]);
	}	
	
	printf("%d\n", A[best]);
	int rez = best;
	FOR(i,1,A[rez])
	{
		printf("%d ",best);
		best = T[best];
	}	
	return 0;
}