Pagini recente » Cod sursa (job #2602722) | Cod sursa (job #2478213) | Cod sursa (job #2701369) | Cod sursa (job #174213) | Cod sursa (job #50230)
Cod sursa(job #50230)
# 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>=poz)
{
lnnou=poz;
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",lnnou);
long int i;
for (i=1;i<=lnnou-1;i++)
fprintf(g,"%ld ",sol2[i]);
fprintf(g,"%ld\n",sol2[lnnou]);
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;
}