Cod sursa(job #14988)

Utilizator raula_sanChis Raoul raula_san Data 10 februarie 2007 14:49:32
Problema Subsir 2 Scor 47
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include<cstdio>

#define dim 5005

int N;

long A[dim], B[dim], P[dim];

void binary_s( int, int, long );

int main()
{
	freopen("subsir2.in", "r", stdin);
	freopen("subsir2.out", "w", stdout);
	
	int i, k=0;
	
	scanf("%d", &N);
	for(i=1; i<=N; ++i) scanf("%ld", A+i);
	
	for(i=1; i<=N; ++i)
	{
		if( A[i] >= B[k] ) B[++k] = A[i], P[k] = i;
		else
			binary_s(k, i, A[i]);
	}
	
	printf("%d\n", k);
	for(i=1; i<=k; ++i) printf("%ld ", P[i]);
	
	fclose(stdin); fclose(stdout);
    return 0;
}

void binary_s( int N, int p, long value )
{
	int st, dr, m=(1+N)>>1;
	
	for(st=1,dr=N; st<=dr; m=(st+dr)>>1)
	{
		if(m == N && B[N] > value && B[N-1] <= value)
			B[N] = value, P[N] = p;
		else if(m < N && B[m] <= value && B[m+1] > value)
			B[m+1] = value, P[m+1] = p;
		else
		{
			if(value >= B[m]) st = m+1;
			if(value <  B[m]) dr = m-1;
		}
	}
}