Cod sursa(job #203745)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 19 august 2008 11:41:57
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 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;
short int A[N_MAX],T[N_MAX];
int V[N_MAX];
char ch[1<<19];

int main()
{
	int k(0),semn(0);
	freopen(IN, "r",stdin);
	freopen(OUT, "w",stdout);
	scanf("%d\n", &N);
	fgets(ch,1<<19,stdin);
	FOR(i,1,N)
	{
		if(ch[k] == '-')
			++k,semn=i;
		while(ch[k] <= '9' && ch[k] >= '0')
			V[i] = V[i] * 10 + ch[k] - '0',++k;
		++k;
		if(semn == i)
			V[i] *= -1;
	}	
	
	int best(0),minim(1<<21);
	A[0] = 1<<13;
	V[0] = 1<<21;
	for(int i=N;i>=1;--i)
	{
		FOR(j,i+1,N)
			if(V[j] >= V[i])
			{
				if(V[j] < minim && (A[j] < A[best] || (A[j] == A[best] && V[j] < V[best])) )
					best = j;
				minim = min(minim,V[j]);
			}	
		if(best)
			A[i] = A[best] + 1,
			T[i] = best;
		else
			A[i] = 1;
		best = 0;
		minim = 1<<21;	
	}	
	
	FOR(i,1,N)
	{
		if(V[i] < minim && (A[i] < A[best] ||  (A[i] == A[best] && V[i] < V[best])))
			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;
}