Cod sursa(job #594600)

Utilizator rudarelLup Ionut rudarel Data 8 iunie 2011 15:15:39
Problema Secv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 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;
}