Pagini recente » Cod sursa (job #1879133) | Cod sursa (job #1573221) | Cod sursa (job #2700174) | Cod sursa (job #83861) | Cod sursa (job #2236086)
#include<cstdio>
#include<fstream>
#include<algorithm>
using namespace std;
FILE *f=fopen("subsir2.in","r");
ofstream g("subsir2.out");
int v[5002],l[5002],ant[5002],r[5002],maxim[5002];
int n,len;
void scmax(int id)
{
int st,dr,mij,ans=0;
st=0;
dr=len;
while(st<=dr)
{
mij=(st+dr)/2;
if(v[l[mij]]<=v[id])
{
st=mij+1;
ans=mij;
}
else
dr=mij-1;
}
if(v[l[ans+1]]>v[id]||ans==len)
l[ans+1]=id;
len=max(len,ans+1);
ant[id]=l[ans];
}
void reconstituire()
{
int i=l[len],ll=len;
while(i!=0)
{
r[len--]=i;
i=ant[i];
}
len=ll;
}
int main()
{
int i,sol;
fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
fscanf(f,"%d",&v[i]);
v[0]=v[n+1]=-1000002;
for(i=n;i>=1;i--)
maxim[i]=max(v[i],maxim[i+1]);
sol=n+1;
for(i=1;i<=n;i++)
{
scmax(i);
if(v[i]>maxim[i+1]&&sol>=len)
{
sol=len;
reconstituire();
}
}
len=sol;
g<<len<<'\n';
for(i=1;i<=len;i++)
g<<r[i]<<" ";
return 0;
}