Pagini recente » Cod sursa (job #671127) | Cod sursa (job #1804946) | Cod sursa (job #253867) | Cod sursa (job #3152634) | Cod sursa (job #14990)
Cod sursa(job #14990)
#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(B[m] == value) return;
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;
}
}
}