Pagini recente » Cod sursa (job #1819768) | Cod sursa (job #1619433) | Cod sursa (job #995985) | Cod sursa (job #3260640) | Cod sursa (job #950442)
Cod sursa(job #950442)
#include <fstream>
using namespace std;
ifstream fin ("subsir2.in");
ofstream fout ("subsir2.out");
int s[5001],l,v[5001],n,i,ls,ld,m,ind[5001],j,succ[5001];
int main ()
{
fin>>n;
for (i=1;i<=n;i++) fin>>v[i];
succ[n]=0;
for (i=n-1;i>=1;i--)
{
for (j=i+1;j<=n;j++)
{
if (v[i]<=v[j]) {succ[i]=succ[j]+1; break;}
}
}
s[1]=v[1]; l=1; ind[1]=1;
for (i=2;i<=n;i++)
{
if (v[i]>=s[l]) {s[++l]=v[i]; ind[l]=i;}
else
{
ls=1; ld=l;
while (ls<ld)
{
m=(ls+ld)/2;
if (v[i]>s[m]) ls=m+1;
else ld=m-1;
}
while (s[ls]<=v[i]) ls++;
if (succ[i]<succ[ind[ls]])
{
s[ls]=v[i];
l=ls;
ind[l]=i;
}
}
}
fout<<l<<"\n";
for (i=1;i<=l;i++) fout<<ind[i]<<" ";
}