Pagini recente » Cod sursa (job #2581264) | Cod sursa (job #2458300) | Cod sursa (job #1687981) | Cod sursa (job #2357009) | Cod sursa (job #707863)
Cod sursa(job #707863)
#include<stdio.h>
static int lung[100000],v[100000],leg[100000];
int caut_binar(int nr,int st,int dr)
{
int ult_completat=dr,mij;
while(st<dr)
{
mij=(st + dr)/2;
if(v[lung[mij]] <=nr)
st=mij +1;
else dr=mij;
}
while(v[lung[mij]] >=nr)
--mij;
leg[++ult_completat]=mij;
lung[ult_completat]=lung[mij]+1;
}
void afis_rec(FILE *g,int ult_completat,int poz)
{
if(ult_completat==0)
return;
afis_rec(g,--ult_completat,leg[poz]);
fprintf(g,"%i ",v[poz]);
}
int main()
{
int n,i,j;
FILE *f=fopen("scmax.in","rt");
FILE *g=fopen("scmax.out","wt");
fscanf(f,"%i",&n);
for(i=0;i<n;i++)
fscanf(f,"%i",&v[i]);
fclose(f);
lung[0]=0;
int ult_completat=0;
leg[0]=-1;
for(i=1;i<n;i++)
{
if(v[i]>v[lung[ult_completat]])
{
lung[++ult_completat]=i;
leg[i]=lung[ult_completat-1];
}
else
{
j=ult_completat;
while(j!=-1 && v[lung[j]]>=v[i] )
j--;
lung[++j] = i;
if(j==0)
leg[i]=-1;
else
leg[i]=lung[j-1];
}
}
fprintf(g,"%i\n",ult_completat+1);
int poz=lung[ult_completat];
ult_completat++;
afis_rec(g,ult_completat,poz);
fclose(g);
return 0;
}