Cod sursa(job #2243119)

Utilizator bleo16783FMI Bleotiu Cristian bleo16783 Data 19 septembrie 2018 22:12:26
Problema Subsir 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <iostream>
#include<fstream>
#include<vector>
using namespace std;
#define N 5005
#define MX 2000200
#define f first
#define s second
#define pb push_back
int v[N],i,j,n,pmn,mx,d[N],nxt[N],mn,curr;
bool ok[N];
vector<int>F;
vector<int>sol;
vector<int>S;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
int put(int x)
{
    if(!sol.size())
    {
        sol.pb(x);
        return 1;
    }
    if(sol[sol.size()-1]<x)
    {
        sol.pb(x);
        return sol.size();
    }
    int p=0;
    for(int a=sol.size()-1;a>0;a>>=1)
        while(a+p<sol.size()&&sol[p+a]<=x)p+=a;
    sol[p+1]=x;
    return p+2;
}
int main()
{
    fin>>n;
    for(i=0;i<n;++i)
        fin>>v[i];
    mx=0;
    for(i=n-1;i>-1;--i)
        if(v[i]>mx)
            F.pb(i),mx=v[i];
    for(i=0;i<n;++i)
        d[i]=put(v[i]);
    mn=MX;
    for(i=0;i<F.size();++i)
    if(d[F[i]]<mn)pmn=F[i],mn=d[F[i]];
    fout<<mn<<'\n';
    S.pb(pmn+1);
    curr=pmn;
    for(i=curr-1;i>-1;--i)
        if(d[i]==d[curr]-1)
        {
            S.pb(i+1);
            curr=i;
        }
    for(i=mn-1;i>-1;--i)
        fout<<S[i]<<' ';
    return 0;
}