Cod sursa(job #2574447)

Utilizator Alex2421Nedelcu Alexandru Alex2421 Data 5 martie 2020 22:24:28
Problema Subsir crescator maximal Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("scmax.in");
ofstream out("scmax.out");

int const lim = 100001;
int n,v[lim],d[lim],t,mx;
struct ob
{
    int poz,vl;
}c[lim];
vector < int > q;

bool comp(ob x, ob y)
{
    return x.vl<y.vl;
}

int caut(int val , int st , int dr)
{
    int mij=(st+dr)/2;
    if(c[mij].vl<val && c[mij+1].vl>=val)
        return c[mij].poz;
    if(c[mij].vl<val && mij==t)
        return c[mij].poz;
    if(c[mij].vl<val && c[mij+1].vl<val)
        return caut(val,mij+1,dr);
    if(c[mij].vl>=val && mij>1)
        return caut(val,st,mij);

     return -1;
}

int main()
{
    in>>n;
    for(int i=1;i<=n;i++)
    {
        in>>v[i];
    }

    d[1]=1;
    t++;
    c[t].vl=v[1];
    c[t].poz=1;
    for(int i=2;i<=n;i++)
    {
        sort(c+1,c+1+t,comp);
        int x=caut(v[i],1,t);

       if(x==-1)
        d[i]=1;
       else
        d[i]=d[x]+1;

       t++;
       c[t].vl=v[i];
       c[t].poz=i;
       if(d[i]>mx) mx=d[i];
    }

    out<<mx<<'\n';
    for(int i=n;i>=1;i--)
        if(d[i]==mx)
        {
            q.push_back(v[i]);
            mx--;
        }

    for(int i=q.size()-1;i>=0;i--)
            out<<q[i]<<" ";
}