Cod sursa(job #2026628)

Utilizator Garen456Paun Tudor Garen456 Data 24 septembrie 2017 19:10:44
Problema Subsir 2 Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <fstream>

using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
int n,a[5005],q[5005],miz,mic,b[5005],cat,x[5005];
bool capat[5005],c[5005][5005];
int main()
{   int i,j,mini,ok,ma,z;
    fin>>n;
    for(i=1;i<=n;++i)
        fin>>a[i];
    mini=1; q[1]=1; capat[1]=1;
    for(i=2;i<=n;++i)
    { ok=0; ma=0; capat[i]=1; q[i]=1;
        for(j=i-1;j>=1;--j)
        if(ok==1 )
             {if(a[j]>ma &&  a[j]<=a[i])
             { capat[j]=0; ma=a[j];
            // fout<<q[j]+1<<" ";
                if(q[j]+1<=q[i])
             {  q[i]=q[j]+1;
               ma=a[j];
               c[i][j]=1;  //fout<<i<<"si"<<j<<";; ";
               capat[j]=0;
             }
             }
             }

       else   if(ok==0)
               if(a[j]<=a[i])
               { ok=1; ma=a[j];
                   capat[j]=0;
                   q[i]=q[j]+1; c[i][j]=1;
                  // fout<<i<<"si"<<j<<"; ";
               }


       if(!ok)
            mini=i;
           // fout<<"\n\n";


    }


for(i=1;i<=n;++i)
        if(capat[i])
    if(miz==0)
           miz=q[i];
        else if(q[i]<miz)
            miz=q[i];
    fout<<miz<<"\n"; ok=0;
 for(i=1;i<=n;++i)
      if(capat[i] && q[i]==miz)
        {
   b[miz]=i; int minz;
   j=miz-1;
   while(j)
   {  minz=0;
       for(z=b[j+1]-1;z>=1;--z)
         if(!capat[z] && q[b[j+1]]-1==q[z] && a[b[j+1]]>=a[z])
            if(c[b[j+1]][z])
          if(minz==0) minz=z;
         else if(a[minz]>a[z])
            minz=z;
         b[j]=minz;
      --j;
   }
   if(ok==0)
    for(z=1;z<=miz;++z)
        x[z]=b[z];
   else for(z=1;z<=miz;++z)
           if(x[z]>b[z])
   { for(z=1;z<=miz;++z)
      x[z]=b[z];
       break;
   }

        }
   for(i=1;i<=miz;++i)
    fout<<b[i]<<" ";
    return 0;
}