Cod sursa(job #27429)

Utilizator marius135Dumitran Adrian Marius marius135 Data 6 martie 2007 14:05:36
Problema Secv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include<stdio.h>
#include<stdlib.h>

#define maxn 5120

long poz[maxn];


int sort(const void *a,const void *b)
{
	return *(int *)a-*(int *)b;
}
long cauta(long a,long b,long *v)
{
	long st=1,dr=b;
	while(st!=dr)
		{
		long mij=(st+dr)/2;
		if(v[mij]>=a) dr=mij;
		else st=mij+1;
		}
	return st;
}

long subsir(long *v,long n,long nr,long *t)
{
	long i,a,opt=10000;
	
	for(i=1;i<=n;i++)
		{
		a = cauta(v[i],nr,t);
		if(a==1) poz[1]=i;
		if(a>1) poz[a]=poz[a-1];
		if(a==nr && poz[a] < 10000) if(i-poz[a] <opt) opt = i - poz[a] + 1;
		}
	if(opt>=10000) return -1;
	return opt;
}

int main()
{
	long n,i,v[maxn],t[maxn],nr;
	
	freopen("secv.in","rt",stdin);
	freopen("secv.out","wt",stdout);
	
	scanf("%ld",&n);
	for(i=1;i<=n;i++)
		{
		scanf("%ld",&v[i]);
		t[i]=v[i];
		}
	qsort(t+1,n,sizeof(t[0]),sort);
	nr=1;
	poz[0]=10000;
	for(i=2;i<=n;i++)
		if(t[i]!=t[i-1]) {t[++nr]=t[i];poz[nr]=10000;}
	
	printf("%ld\n",subsir(v,n,nr,t));
	
	
	
	return 0;
}