Cod sursa(job #1371905)

Utilizator tudor_bonifateTudor Bonifate tudor_bonifate Data 4 martie 2015 10:09:28
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
long long a[100001],poz[100001],st[100001],n,i,nr,Max,j,k,x,aux,c[100001];
ifstream f("scmax.in");
ofstream g("scmax.out");
int cautare_binara(int a)
{
    int s=1;
    int d=nr;
    sort(st+1,st+nr+1);
    bool OK=true;
    while (s<=d && OK==true)
    {
        if (st[(s+d)/2]==(a+1)) OK=false;
        else
        {
            if (st[(s+d)/2]>(a+1)) s++;
            else d--;
        }
    }
    if (OK==true) return (s+d)/2;
    else return s;
}
int main()
{
    f>>n;
    for (i=1; i<=n; i++) f>>a[i];
    poz[1]=1;
    st[1]=a[1];
    nr=1;
    for (i=2; i<=n; i++)
    {
        if (a[i]>st[nr])
        {
            st[++nr]=a[i];
            poz[i]=nr;
        }
        else
        {
            if (a[i]!=st[nr])
            {
                x=cautare_binara(a[i]);
                st[x]=a[i];
                poz[i]=x;
            }
            else poz[i]=poz[i-1];
        }
    }
    Max=0;
    for (i=1; i<=n; i++)
    {
        if (poz[i]>Max) Max=poz[i];
    }
    g<<Max<<'\n';
    nr=0;
    for (i=1; i<=n; i++)
    {
        aux=i;;
        if (poz[i]==Max)
        {
            for (k=1; k<=Max; k++)
            {
                c[++nr]=a[aux];
                for (j=aux; j>=1; j--) if (a[j]<a[aux] && poz[j]==(poz[aux]-1))
                    {
                        break;
                    }
                aux=j;
            }
        }
    }
    for (i=nr; i>=1; i--) g<<c[i]<<' ';
    return 0;
}