Cod sursa(job #49778)

Utilizator damaDamaschin Mihai dama Data 6 aprilie 2007 13:55:40
Problema Subsir 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <stdio.h>

int n, v[5001], a[5001], prev[5001];

void print(int pos);

int main()
{
    freopen("subsir2.in","r",stdin);
    freopen("subsir2.out","w",stdout);

    int i, min, mid, max, cnt, sol, j, m;

    scanf("%d", &n);

    for(i = 1; i <= n; ++i)
    {
        scanf("%d", &v[i]);
    }
    m = 1;

    for(i = 2; i <= n; ++i)
    {
        if(v[i] < v[m])
            m = i;
    }

    a[0] = 0;
    v[0] = -1000001;
    a[1] = m;
    cnt = 1;

    for(i = m + 1; i <= n; ++i)
    {
        min = 0;
        max = cnt;
        sol = cnt;
        while(min <= max)
        {
            mid = (min + max) >> 1;
            if(v[a[mid]] <= v[i])
            {
                min = mid + 1;
                sol = mid;
            }
            else
            {
                max = mid - 1;
            }
        }
        a[sol + 1] = i;
        prev[i] = a[sol];
        if(sol + 1 > cnt)
            cnt = sol + 1;
            /*
        for(j = 1; j <= cnt; ++j)
        {
             printf("%d ", v[a[j]]);
        }
        printf("\n");
        */
    }

    printf("%d\n", cnt);
    print(a[cnt]);

    return 0;
}

void print(int pos)
{
    if(pos)
    {
        print(prev[pos]);
        printf("%d ", pos);
    }
}