Cod sursa(job #206337)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 5 septembrie 2008 22:59:36
Problema Secv Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.89 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;   
}  
#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;
}