Cod sursa(job #2549494)

Utilizator bem.andreiAndrei Bem bem.andrei Data 17 februarie 2020 18:59:16
Problema Subsir crescator maximal Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream r("scmax.in");
ofstream w("scmax.out");
int v[100001], f[100001];
int cautbin(int n)
{
    int st=0, dr=99999, mij, p=1;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]>=n)
        {
            p=mij;
            dr=mij-1;
        }
        else
        {
            st=mij+1;
        }
    }
    return p;
}
int main()
{
    int n, cnt=0, maxim=0, var=1999999999;
    r>>n;
    for(int i=0; i<n; i++)
    {
        int k;
        r>>k;
        if(k>=v[cnt] && k<=var)
        {
            if(k!=v[cnt])
            {
                cnt++;
                v[cnt]=k;
            }
        }
        else
        {
            if(k<v[cnt])
            {
                if(cnt>maxim)
                {
                    maxim=cnt;
                    for(int j=0; j<=cnt; j++)
                    {
                        f[j]=v[j];
                    }
                    var=v[cnt];
                }
                cnt=cautbin(k);
                v[cnt]=k;
            }
            else
            {
                maxim=max(maxim,cnt);
                maxim++;
                f[maxim]=k;
            }
        }
    }
    if(cnt>maxim)
    {
        maxim=cnt;
        for(int j=0; j<=cnt; j++)
        {
            f[j]=v[j];
        }
    }
    w<<maxim<<"\n";
    for(int i=1; i<=maxim; i++)
    {
        w<<f[i]<<" ";
    }
    return 0;
}