Cod sursa(job #876161)

Utilizator superman_01Avramescu Cristian superman_01 Data 11 februarie 2013 14:23:38
Problema Subsir 2 Scor 54
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 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]);
     
}
 

 
inline void write ( void )
{
     
    int minimum=-1<<30;
    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;
     
}