Cod sursa(job #203728)

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

#include <cstdio>
#include <algorithm>
#include<stdlib.h>  

#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],*s;

void scan()
{
	freopen(IN, "r",stdin);
	freopen(OUT, "w",stdout);
	scanf("%d\n", &N);
	fgets(ch,1<<20,stdin);    
    s=ch;    
    FOR(i,1,N-1)    
    {   
        V[i] = atol(s);    
        s=strchr(s,' ');    
        s++;    
    }    
    V[N]=atol(s);   
}

void solve()
{
	int best,minim;
	A[0] = 1<<20;
	V[0] = 1<<20;
	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<<20;
		
	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];
	}	
}

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