Pagini recente » Cod sursa (job #327263) | Cod sursa (job #58117) | Cod sursa (job #1699819) | Cod sursa (job #683126) | Cod sursa (job #50226)
Cod sursa(job #50226)
# include <stdio.h>
const int MAXN=5000;
long int n,stack[MAXN+1],card[MAXN+1],stacklen,v[MAXN+1],sol[MAXN+1],sol2[MAXN+1],ls;
int maximum[MAXN+1];
long int nnou,lnnou;
void citire()
{
FILE *f=fopen("subsir2.in","r");
fscanf(f,"%ld",&n);
long int i;
for (i=1;i<=n;i++) fscanf(f,"%ld",&v[i]);
fclose(f);
}
long int find(long int val)
{
long int li=1,lf=stacklen,mij;
while (li<=lf)
{
mij=(li+lf)/2;
if (stack[mij]>val&&(mij-1==0||stack[mij-1]<val)) return mij;
else if (stack[mij]<val) li=mij+1;
else lf=mij-1;
}
return ++stacklen;
}
void calculeaza()
{
long int i,poz;lnnou=n+1;
for (i=1;i<=n;i++)
{
poz=find(v[i]);
stack[poz]=v[i];
card[i]=poz;
if (maximum[i])
if (lnnou>=stacklen)
{
lnnou=stacklen;
nnou=i;
}
}
}
void pick_solution()
{
long int i;
for (i=1;i<=nnou;i++) sol[i]=1000001;
for (i=1;i<=nnou;i++)
if (sol[card[i]]>v[i])
{
sol[card[i]]=v[i];
sol2[card[i]]=i;
}
}
void scrie()
{
FILE *g=fopen("subsir2.out","w");
fprintf(g,"%ld\n",stacklen);
long int i;
for (i=1;i<=stacklen-1;i++)
fprintf(g,"%ld ",sol2[i]);
fprintf(g,"%ld\n",sol2[stacklen]);
fcloseall();
}
void set_maximum()
{
long int i=n-1,y=v[n];
maximum[n]=1;
while (i)
{
if (y<v[i])
{
maximum[i]=1;
y=v[i];
}
i--;
}
}
int main()
{
citire();
set_maximum();
calculeaza();
//elim_backgroundless();
pick_solution();
scrie();
return 0;
}