Cod sursa(job #1946266)

Utilizator KOzarmOvidiu Badea KOzarm Data 30 martie 2017 00:14:00
Problema Subsir crescator maximal Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>

using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");

int a[100003],b[100003],c[100003],n;



void plaseaza(int x,int poz)
{
    int p=b[0]+1;
    int in=1,fi=b[0];
    while(in<=fi)
    {
        int mid=(in+fi)/2;
        if(a[b[mid]]>x)
        {
            p=mid;
            fi=mid-1;
        }
        else
        if(a[b[mid]]==x)
        {
            p=0;
            fi=0;
        }
        else
            in=mid+1;
    }
    if(p==b[0]+1)
    {
        b[0]++;
        b[b[0]]=poz;
        if(poz>1)
            c[poz]=b[b[0]-1];
    }
    else
    if(p!=0)
    {
        b[p]=poz;
        if(p>1)
            c[poz]=b[p-1];
    }
}

void afisare(int poz)
{
    if(c[poz]!=0)
        afisare(c[poz]);
    fout<<a[poz]<<" ";
}


int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>a[i];
        plaseaza(a[i],i);
    }
    fout<<b[0]<<"\n";
    afisare(b[b[0]]);
    return 0;
}