Cod sursa(job #2236086)

Utilizator armigheGheorghe Liviu Armand armighe Data 28 august 2018 08:27:53
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<cstdio>
#include<fstream>
#include<algorithm>
using namespace std;
FILE *f=fopen("subsir2.in","r");
ofstream g("subsir2.out");
int v[5002],l[5002],ant[5002],r[5002],maxim[5002];
int n,len;

void scmax(int id)
{
    int st,dr,mij,ans=0;
    st=0;
    dr=len;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[l[mij]]<=v[id])
        {
            st=mij+1;
            ans=mij;
        }
        else
            dr=mij-1;
    }
    if(v[l[ans+1]]>v[id]||ans==len)
        l[ans+1]=id;
    len=max(len,ans+1);
    ant[id]=l[ans];
}

void reconstituire()
{
    int i=l[len],ll=len;
    while(i!=0)
    {
        r[len--]=i;
        i=ant[i];
    }
    len=ll;
}

int main()
{
    int i,sol;
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++)
        fscanf(f,"%d",&v[i]);
    v[0]=v[n+1]=-1000002;
    for(i=n;i>=1;i--)
        maxim[i]=max(v[i],maxim[i+1]);
    sol=n+1;
    for(i=1;i<=n;i++)
    {
        scmax(i);
        if(v[i]>maxim[i+1]&&sol>=len)
        {
            sol=len;
            reconstituire();
        }
    }
    len=sol;
    g<<len<<'\n';
    for(i=1;i<=len;i++)
        g<<r[i]<<" ";
    return 0;
}