Cod sursa(job #2669571)

Utilizator NeacsuMihaiNeacsu Mihai NeacsuMihai Data 7 noiembrie 2020 11:36:42
Problema Subsir 2 Scor 45
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("subsir2.in");
ofstream fout ("subsir2.out");

int v[5001], o[5001], h[5001], afis[5001];
int main()
{
    int n, i, k, t, p, u, mij, nr_afis;
    fin>>n;
    for(i=1; i<=n; i++)
    {
        fin>>v[i];
    }
    k=0;
    for(i=1; i<=n; i++)
    {
        if(v[i]>=o[k])
        {
            k++;
            t=k;
        }
        else
        {
            p=1;
            u=k;
            while(p<=u)
            {
                mij=(p+u)/2;
                if(v[i]<o[mij])
                {
                    t=mij;
                    u=mij-1;
                }
                else p=mij+1;
            }
        }
        o[t]=v[i];
        h[i]=t;
    }
    fout<<t<<"\n";
    nr_afis=0;
    for(i=n; i>=1 && t>0; i--)
    {
        if(h[i]==t)
        {
            afis[++nr_afis]=i;
            t--;
        }
    }
    for(i=nr_afis; i>=1; i--) fout<<afis[i]<<' ';
}