Cod sursa(job #876390)

Utilizator superman_01Avramescu Cristian superman_01 Data 11 februarie 2013 19:42:42
Problema Subsir 2 Scor 59
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 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(check[i]==true)
    {
        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;
		check[i]=true;
        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];
                   
									
                   check[j]=false;
              
            }
          
        }
          
          
          
          
    }
    write();   
      
}
int main()
{
    read();
    solve();
    return 0;
      
}