Cod sursa(job #1127699)

Utilizator raztaapDumitru raztaap Data 27 februarie 2014 13:29:03
Problema Subsir crescator maximal Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <cstdio>
#include <algorithm>
using namespace std;
int v[1030], q[1030], p[1030], poz, lg, s[1030], n, nr,MAX;
void citire()
{
    int i;
    scanf("%d", &n);
    for(i=1;i<=n;++i)
        scanf("%d", &v[i]);
}
int insert(int k, int lo, int hi)
{
    int mid=(lo+hi)/2;
    if(lo==hi)
    {
        if(hi>lg)
            q[++lg+1]=MAX;
        q[lo]=k;
        return lo;
    }
    else
        if(k<q[mid]) return insert(k, lo, mid);
        else
            return insert(k, mid+1, hi);
}
void construire_S()
{
    int i=lg;
    int poz=n;
    while(i)
    {
        while(poz)
        {
            if(p[poz]==i)
            {
                s[++nr]=v[poz];
                break;
            }
            poz--;
        }
        i--;
    }
}
void afisare()
{
    int i;
    printf("%d\n", lg);
    for(i=nr;i>=1;--i)
        printf("%d ", s[i]);
}
void construire_QP()
{
    int i;
    for(i=1;i<=n;++i)
    {
        if(!binary_search(q+1, q+lg+1, v[i]))
            p[i]=insert(v[i], 1, lg+1);
    }
}
void rezolva_problema()
{
    citire();
    construire_QP();
    construire_S();
    afisare();
}
int main()
{
    freopen("scmax.in", "r", stdin);
    freopen("scmax.out", "w", stdout);
    MAX=300;
    rezolva_problema();
    return 0;
}