Cod sursa(job #2511904)

Utilizator darisavuSavu Daria darisavu Data 20 decembrie 2019 09:05:16
Problema Subsir crescator maximal Scor 65
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.64 kb
#include <fstream>

using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int a[100005],d[100005],n,i,z,p;
int caut_bin(int x)
{
    int st=1,dr=z,mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(a[d[mij]]<x) st=mij+1;
        else dr=mij-1;
    }
    return st;
}
void afis(int nr)
{
    if(nr>0)
    {
        afis(nr-1);
        g<<a[d[nr]]<<" ";
    }
}
int main()
{
    f>>n;
    for(i=1;i<=n;i++) f>>a[i];
    for(i=1;i<=n;i++)
    {
        p=caut_bin(a[i]);
        if(p>z) {z++; d[z]=i;}
        else if(a[i]<a[d[p]]) d[p]=i;
    }
    g<<z<<'\n';
    afis(z);
    return 0;
}