Cod sursa(job #206330)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 5 septembrie 2008 22:33:16
Problema Secv Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <stdio.h>

#define FIN "secv.in"
#define FOUT "secv.out"

#define NMAX 5000
#define MAXN 5000

#define MINIM 0x3f3f3f3f
#define INF 666666

int N;
int v[NMAX];
int v1[NMAX];
int v2[MAXN];
int REZ;
int i,j,mij;
int frecv[MAXN];
int nr;

void swap(int a, int b)
{

int aux=a;
    a=b;
    b=aux;
}


void quicksort(int li, int ls)
{

i=li;
j=ls;
mij=v[(li+ls)/2];

do
  {
   while (v[j]>mij) --j;
   while (v[i]<mij) ++i;
   if (i<=j)
      {
       swap(v[i],v[j]);
       ++i;
       --j;
	}
   }
while (i<=j);
if (li<j) quicksort(li,j);
if (i<ls) quicksort(i,ls);
}


void read_data()
{

freopen(FIN,"rt",stdin);
scanf("%d", &N);

for (i=0;i<N;++i)
     {
      scanf("%d", &v[i]);
      v1[i]=v[i];
      }
}


void solve()
{

nr=1;
frecv[v[0]]=1;
for (i=1;i<N;++i)
     if (v[i]!=v[i-1])
	  {
	   nr++;
	   frecv[v[i]]=nr;
	   }


REZ=INF;

for (i=0;i<nr;++i)
     v2[i]=-INF;

for (i=0;i<=N;++i)
     {
      if (frecv[v1[i]]==1)
	  v2[i]=i;
	  else
	  v2[frecv[v1[i]]]=v2[frecv[v1[i]]-1];
      if (i-v2[nr]<REZ)
	  REZ=i-v2[i];
      }

freopen(FOUT,"wt",stdout);
if (REZ!=INF)
    printf("%d",REZ-1);
    else
    printf("-1");
}

int main()
{
read_data();
solve();
printf("\n");
return 0;
}