Cod sursa(job #824035)

Utilizator lucky1992Ion Ion lucky1992 Data 25 noiembrie 2012 20:13:38
Problema Subsir crescator maximal Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.8 kb
#include <stdlib.h>
#include <stdio.h>
#include <string.h>



int bineary_search( int *v, int *M, int left, int right, int x ){
  
  int aux = right;
  int mid = ( left + right ) / 2;
  while ( left <= right ){
    if( ( v[M[mid]] < x ) && ( x <= v[M[mid+1]] ) ) return mid;
    else if( x > v[M[mid+1]] ){ 
      left = mid + 1; 
      mid = ( left + right ) / 2; 
    }
    else{ 
      right = mid - 1; 
      mid = ( left + right ) / 2 ; 
    }
  }
  return aux;
}




int main( int argc, char* argv[] ){
  
  FILE* in;
  FILE* out;
  
  in = fopen("scmax.in","r");
  out = fopen("scmax.out","w");
  
  int N; if(fscanf(in,"%d",&N));
  int nr = 1; // initial length
  int max = 0;
  int p = 0, i = 0, idx = 0;
  int* v = (int*)malloc( sizeof(int)*(N+1) );
  int* M = (int*)malloc( sizeof(int)*(N+1) );
  int* best = (int*)malloc( sizeof(int)*(N+1) );
  int* prev = (int*)malloc( sizeof(int)*(N+1) );;
  int* stack = (int*)malloc( sizeof(int)*(N+1) );
  
  v[0] = 0; // dummy value = 0 
  for( i = 1; i <= N; i++ )
    if( fscanf(in,"%d",&v[i]) );
  fclose(in);
  M[0] = 0; // dummy value = 0 
  M[1] = 1; // for v[1]
  memset( best, 1, (N+1)*sizeof(int) );
  memset( prev, -1, (N+1)*sizeof(int) );
  
 for( i = 2; i <= N; i++ ){
    
    idx = bineary_search( v, M, 0, nr, v[i] );
    M[idx+1] = i;
    prev[i] = M[idx]; // introduc in prev[i] cel mai mare element mai mic decat noul el introdus v[i]
    best[i] = idx + 1;
    
    if( best[i] > max ){
      max = best[i];
      p = i;
    }
        
    if( nr < idx + 1 ) 
      nr++;
    
    
  }
  
  fprintf(out,"%d\n",max);
  
  int k = 0;
  while ( p > 0 ){
    stack[k++] = v[p];
    p = prev[p];
    
  }

  
  for( i = k-1 ; i >= 0 ; i-- )
    fprintf(out,"%d ", stack[i] );
  
  fclose(out);
  free(v);
  free(M);
  free(best);
  free(prev);
  free(stack);
  
  return 0;
}