Cod sursa(job #203726)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 19 august 2008 01:13:01
Problema Subsir 2 Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
using namespace std;

#include <cstdio>
#include <algorithm>

#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[(N_MAX)*5];

inline int better(int x,int y)
{
	int l = A[x];
	FOR(i,1,l)
	{
		if(V[x] < V[y])
			return 1;
		if(V[y] < V[x])
			return 0;
		x = T[x];
		y = T[y];
	}
	return 0;
}

void scan()
{
	freopen(IN, "r",stdin);
	freopen(OUT, "w",stdout);
	scanf("%d\n", &N);
	FOR(i,1,N)
		scanf("%d", &V[i]);
}

void solve()
{
	int best,minim;
	A[0] = 1<<30;
	V[0] = 1<<30;
	bool ok;
	for(int i=N;i>=1;--i)
	{
		best = ok = false;
		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<<30;
		
	FOR(i,1,N)
	{
		if( (A[i] < A[best] ||  (A[i] == A[best] && better(i,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];
	}	
}

int main()
{
	scan();
	solve();
	return 0;
}