Cod sursa(job #2674218)

Utilizator Rowantoie vlad Rowan Data 18 noiembrie 2020 20:10:49
Problema Subsir crescator maximal Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
//
//  main.cpp
//  scmax
//
//  Created by Toie Vlad on 18/11/2020.
//

#include <iostream>
#include <vector>
#include <fstream>
#define MAX_N 100005

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

int n, v[MAX_N], best[MAX_N], p[MAX_N], maxim, k, L[MAX_N], nr;

void afis(int i) {
    if(p[i] > 0) {
        afis(p[i]);
    }
    fout<<v[i]<<" ";
}
    
int cautBin(int x) {
    int l, r, m;
    l = 0;
    r = nr;
    m = (l+r)/2;
    while (l <= r)
    {
      if (v[L[m]] < x &&  v[L[m+1]] >= x)
          return m;
      else if (v[L[m+1]] < x) {
          l = m + 1;
          m = (l + r)/2;
      }
      else {
          r = m - 1;
          m = (l + r)/2;
      }
    }
    return nr;
}
    
 
    
int main()
{
    int i, poz;
    nr = 1;
    fin>>n;
    for (i = 1; i <= n; i++) {
        fin>>v[i];
    }
    L[0] =  0;
    best[1] = L[1] = 1;
    
    for (i = 2; i <= n; i++)
    {
      poz = cautBin(v[i]);
      p[i] = L[poz];
      best[i] = poz + 1;
      L[poz + 1] = i;
      if (nr < poz + 1)
          nr = poz + 1;
    }
    
    maxim = 0;
    poz = 0;
    
    for (i = 1; i <= n; i++) {
       if (maxim < best[i]) {
           maxim = best[i];
           poz = i;
       }
    }
    
    fout<<maxim<<endl;
    
    afis(poz);
    
    fout<<endl;
    
    return 0;
}