Cod sursa(job #2696290)

Utilizator mihaipriboimihailucapriboi mihaipriboi Data 15 ianuarie 2021 17:47:30
Problema Subsir crescator maximal Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
// Mihai Priboi

#include <bits/stdc++.h>

#define MAXN 100000

int v[MAXN], best[MAXN], prev[MAXN], r[MAXN];

int cautbin( int x, int n ) {
  int r, step;
  r = -1;
  step = 1 << 16;
  while( step > 0 ) {
    if( r + step <= n && v[best[r + step]] < x )
      r += step;
    step /= 2;
  }
  return r;
}

int main() {
  FILE *fin, *fout;
  int n, i, j, max, x;
  fin = fopen( "scmax.in", "r" );
  fscanf( fin, "%d", &n );

  for( i = 0; i < n; i++ )
    fscanf( fin, "%d", &v[i] );

  fclose( fin );

  max = 0;
  for( i = 0; i < n; i++ ) {
    x = cautbin( v[i], max - 1 ) + 1;
    best[x] = i;
    max = std::max( x + 1, max );
    if( x > 0 )
      prev[i] = best[x - 1];
    else
      prev[i] = -1;
  }

  j = 0;
  i = best[max - 1];
  while( i > -1 ) {
    r[j++] = v[i];
    i = prev[i];
  }

  fout = fopen( "scmax.out", "w" );

  fprintf( fout, "%d\n", max );
  for( i = max - 1; i >= 0; i-- )
    fprintf( fout, "%d ", r[i] );

  fclose( fout );
  return 0;
}