Cod sursa(job #2695428)

Utilizator mihaipriboimihailucapriboi mihaipriboi Data 12 ianuarie 2021 22:39:44
Problema Subsir crescator maximal Scor 65
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
// Mihai Priboi

#include <bits/stdc++.h>

#define MAXN 100000

int v[MAXN], best[MAXN];

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

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

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

  fclose( fin );

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

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

  fprintf( fout, "%d\n", maxl - 1 );
  for( i = 1; i < maxl; i++ )
    fprintf( fout, "%d ", best[i] );

  fclose( fout );
  return 0;
}