Pagini recente » Cod sursa (job #3244190) | Cod sursa (job #3215850) | Cod sursa (job #628206) | Cod sursa (job #1077531) | Cod sursa (job #1761165)
#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)
{
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();
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;
}