Cod sursa(job #1761694)

Utilizator andrei1299Ghiorghe Andrei Alexandru andrei1299 Data 22 septembrie 2016 18:45:43
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <bits/stdc++.h>

using namespace std;
int a[5005],n,t,sub[5005],val[5005],poss=5005,s;

void Citire()
{
    ifstream fin("subsir2.in");
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>a[i];
    fin.close();
}

void Solutie()
{
    int i,mij,st,dr;
    val[++t]=1;
    for(i=2;i<=n;i++)
    {
        if(a[i]>a[val[t]])
        {
            val[++t]=i;
            sub[i]=val[t-1];
            poss=i;
        }
        else
        {
            st=1;
            dr=t;
            while(st<=dr)
            {
                if(st==1&&dr==2) mij=dr;
                else mij=(st+dr)/2;
                if(a[val[mij-1]]<a[i] && a[val[mij]]>=a[i])
                {
                    val[mij]=i;
                    sub[i]=val[mij-1];
                    if(mij==t) poss=i;
                    break;
                }
                else if(a[val[mij]]<a[i])
                {
                    st=mij+1;
                }
                else
                    dr=mij-1;
            }
        }
    }
}

ofstream fout("subsir2.out");

void rec(int x)
{
    s++;
    if(sub[x]==0) fout<<s<<"\n";
    else rec(sub[x]);
    fout<<x<<" ";
}

void Afisare()
{
    rec(poss);

}

int main()
{
    Citire();
    a[0]=-1000005;
    Solutie();
    Afisare();
    /*for(int i=1;i<=n;i++)
        cout<<sub[i]<<" ";
        cout<<"\n";
    for(int j=1;j<=t;j++)
        cout<<val[j]<<" ";
        cout<<"\n";*/
        fout.close();
    return 0;
}