Cod sursa(job #2958547)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 26 decembrie 2022 21:52:03
Problema Subsir 2 Scor 2
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<fstream>
using namespace std;
ifstream F("subsir2.in");
ofstream G("subsir2.out");
int n,i,a[5001],l[5001],p[5001],m,j,k,t,d[5001],c[5001],r,b[5001];
int main()
{
    for(F>>n,i=1;i<=n;F>>a[i++]);
    for(l[n]=1,i=n-1;i;l[i]=l[i]==n?1:l[i],--i)
        for(m=1e6,l[i]=n,j=i+1;j<=n;++j)
            if(a[j]>=a[i]&&a[j]<m)
                if(m=a[j],l[i]>=l[j]+1)
                    l[i]=l[j]+1,p[i]=j;
    //for(i=1;i<=n;G<<i<<' '<<a[i]<<' '<<l[i]<<' '<<p[i]<<'\n',++i);
    for(r=n+1,i=1;i<=n;++i)
        if(!b[i]) {
            for(m=0,j=i;j!=p[j];c[++m]=j,++b[j],j=p[j]);
            if(m<r||(m==r&&a[c[1]]<a[d[1]]))
                for(r=m,j=1;j<=r;d[j]=c[j],++j);
        }
    for(G<<r<<'\n',i=1;i<=r;G<<d[i++]<<' ');
    return 0;
}