Cod sursa(job #1658299)

Utilizator flaviu_2001Craciun Ioan-Flaviu flaviu_2001 Data 21 martie 2016 12:27:44
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <fstream>
#include <algorithm>

using namespace std;

int v[100001], r[100001], q[100001], w[100001];

int main()
{
    FILE * fin = fopen ( "scmax.in", "r" );
    FILE * fout = fopen ( "scmax.out", "w" );
    int m, n, j, i, k, st, dr, mj, p, maxk = 0;
    fscanf ( fin, "%d", &n ), m = n;
    for ( i = 1; i <= n; ++i )
        fscanf ( fin, "%d", &v[i] ), r[i] = v[i];
    sort ( r + 1, r + n + 1 );
    for ( i = 1; i < n; ++i )
    {
        if ( r[i] == r[i + 1] )
            for ( j = i + 1, --n; j <= n; ++j )
                r[j] = r[j + 1];
    }
    /*for ( i = 1; i <= n; ++i )
        printf ( "%d ", r[i] );*/
    for ( i = 1; i <= m; ++i )
    {
        st = 1, dr = n, k = 1;
        for ( mj = ( st + dr ) >> 1; st <= dr; mj = ( st + dr ) >> 1 )
        {
            if ( r[mj] > v[i] )
                dr = mj - 1;
            else if ( r[mj] < v[i] )
                st = mj + 1;
                else break;
        }
        if ( mj == n )
            continue;
        p = i;
        q[1] = v[i];
        while ( mj <= n )
        {
            for ( j = p + 1; j <= m; ++j )
                if ( v[j] == r[mj + 1] )
                {
                    q[++k] = v[j];
                    p = j;
                    if ( k > maxk )
                    {
                        maxk = k;
                        for ( i = 1; i <= k; ++i )
                            w[i] = q[i];
                    }
                    break;
                }
            ++mj;
        }
    }
    printf ( "%d", maxk );
    for ( i = 1; i <= maxk; ++i )
        fprintf (fout, "%d ", w[i] );
    return 0;
}