Cod sursa(job #931290)

Utilizator tudy23Coder Coder tudy23 Data 28 martie 2013 09:42:25
Problema Subsir crescator maximal Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100100;
int n, x[N], norm[N], anter[N];
int arb[N];
struct scmax
{
    int v,ant;
}t[N];
int mx;
void citire()
{
    freopen("scmax.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&x[i]);
        norm[i]=x[i];}
    fclose(stdin);
}
int binary(int v, int st , int dr)
{
    if(st==dr)
        if(anter[st]==v)
            return st;
        else return -1;
    int m=(st+dr)/2;
    if(anter[m]==v)
        return m;
    if(v<anter[m])
        return binary(v,st,m-1);
    return binary(v,m+1,dr);
}
void normalizare()
{
    int k=0,ant=0;
    for(int i=1;i<=n;++i)
    {
        if(norm[i]!=ant)
            k++,ant=norm[i];
        anter[k]=norm[i];
    }
    for(int i=1;i<=n;++i)
        norm[i]=binary(x[i],1,n);
}
void solve()
{
    for(int j=1;j<=n;++j)
        for(int i=0;i<norm[j];++i)
            if(t[i].v+1>t[norm[j]].v){
                t[norm[j]].v=t[i].v+1,t[norm[j]].ant=i;
                if(t[norm[j]].v>t[mx].v)
                    mx=norm[j];
            }
}
void print(int p)
{
    if(t[p].ant!=0)
        print(t[p].ant);
    printf("%d ",anter[p]);
}
void afisare()
{
    freopen("scmax.out","w",stdout);
    printf("%d\n",t[mx].v);
    int k=mx;
    print(k);
    fclose(stdout);
}
int main()
{
    citire();
    sort(norm+1,norm+1+n);
    normalizare();
    solve();
    afisare();
    return 0;
}