Cod sursa(job #875961)

Utilizator superman_01Avramescu Cristian superman_01 Data 11 februarie 2013 01:35:26
Problema Subsir 2 Scor 54
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include<cstdio>

#define MAX_N 50005

FILE *f=fopen("subsir2.in","r");
FILE *g=fopen("subsir2.out","w");

using namespace std;

int n,v[MAX_N],len[MAX_N],next[MAX_N],poz[MAX_N];
bool check[MAX_N];

inline void read ( void )
{
	fscanf(f,"%d",&n);
	
	for( int index(1) ; index <= n; ++index)
		fscanf(f,"%d", &v[index]);
	
}

void PRINTF( int x)
{
	
	
}


inline void write ( void )
{
	
	int minimum=-(n+1);
	int start_position;
	for( int i= 1; i <= n; ++i)
	{
		if(len[i]>minimum)
		{
			minimum=len[i];
			start_position=i;
		}
		else
			if(len[i]==minimum && v[start_position]>v[i])
				start_position=i;
		
	}
	
fprintf(g,"%d\n%d ",len[start_position],start_position);
while(next[start_position]!=start_position)
{
	fprintf(g,"%d ",next[start_position]);
	start_position=next[start_position];
}
	
}	

inline void solve ( void )
{
	
	int i;
	for( i=n; i>=1 ; --i)
	{
		len[i]=1;
		next[i]=i;
		int minim=1<<30;
		int min=1000001;
		for(int j = i+1 ; j <= n ; ++j )
		{
			if( v[j] > v[i])
			{
			if( len[j]<minim && v[j]<min )
				{
					minim=len[j];
					next[i]=j;
					len[i]=len[j]+1;
					
					
				}
				else
				if( len[j]==minim && v[j]<min && v[j] <= v[next[i]])
                     next[i]=j;
				if(v[j]<min)
					min=v[j];
				
				
			
			}
		
		}
		
		
		
		
	}
	write();	
	
}
int main()
{
	read();
	solve();
	return 0;
	
}