Cod sursa(job #1045265)

Utilizator Corina1997Todoran Ana-Corina Corina1997 Data 1 decembrie 2013 11:31:28
Problema Subsir crescator maximal Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <vector>
#include <fstream>
#include <iomanip>
using namespace std;

ifstream is("scmax.in");
ofstream os("scmax.out");

int n, lmax, nr;
vector<long long int> a, L, t;

void Path( int i );
int BinarySearch( int x, int st, int dr );

int main()
{
    is >> n;
    a.resize( n + 1);
    for ( int i = 1; i <= n; i++ )
        is >> a[i];
    L.resize( n + 1);
    t.resize( n + 1);
    for ( int i = 1; i <= n; i++ )
    {
        int j = BinarySearch( i, 1, lmax );
        L[i] = t[j];
        t[j+1] = i;
        lmax = max ( lmax, j + 1 );
    }
    os << lmax << '\n';
    Path( t[lmax] );


    is.close();
    os.close();
    return 0;
}

int BinarySearch( int x, int st, int dr )
{
    int mij;
    while ( st <= dr )
    {
        mij = (st + dr) / 2;
        if ( a[t[mij]] < a[x] )
            st = mij + 1;
        else
            dr = mij - 1;
    }
    return dr;
}

void Path( int i )
{
    if ( i == 0 ) return;
    Path( L[i] );
    os << a[i] << ' ';
}