Pagini recente » Borderou de evaluare (job #3141894) | Cod sursa (job #401988)
Cod sursa(job #401988)
#include <fstream>
using namespace std;
#define nmax 5010
#define max(a,b) ((a>b)?(a):(b))
int n,m,mns;
int pi;
long long a[nmax],ord[nmax];
struct lista
{
int x;
lista *urm;
};
lista *l[nmax];
void add(lista *&f,int x)
{
lista *l=new lista;
l->x=x;
l->urm=f;
f=l;
}
void read()
{
int i;
ifstream f("secv.in");
f>>n;
for(i=1;i<=n;i++)
{
f>>a[i];
ord[i]=a[i];
}
}
int aux[nmax];
void msort(int l,int r)
{
int m=(l+r)/2;
if(l==r)
return;
msort(l,m);
msort(m+1,r);
int k=l-1,i,j;
for(i=l,j=m+1;i<=m||j<=r;)
{
if(j>r || (i<=m && ord[i]<ord[j]))
aux[++k]=ord[i++];
else
aux[++k]=ord[j++];
}
for(i=l;i<=r;i++) ord[i]=aux[i];
}
void aranj()
{
int k,i;
k=0;
for(i=1;i<=n;i++)
{
ord[++k]=ord[i];
while(i<=n&&ord[i]==ord[i+1])
++i;
}
m=k;
}
int cauta(int x)
{
if(ord[1]==x)
return 1;
if(ord[m]==x)
return m;
int mij,st,dr;
st=1,dr=m;
mij=(st+dr)/2;
while(st<=dr)
{
if(ord[mij]==x)
return mij;
else if(ord[mij]<x)
st=mij;
else
dr=mij;
mij=(st+dr)/2;
}
return 0;
}
void find(int i,int pz,int pi)
{
int pmn=nmax;
for(lista *p=l[i];p!=NULL;p=p->urm)
{
if(p->x>pz&&p->x<pmn)
{
pmn=p->x;
}
}
if(pmn==nmax)
return;
if(i==m)
{
if(pmn!=nmax&&pmn-pi<mns)
{
mns=pmn-pi;
}
return;
}
find(i+1,pmn,pi);
}
void solve()
{
msort(1,n);
aranj();
int i,j;
for(i=1;i<=n;i++)
{
j=cauta(a[i]);
add(l[j],i);
}
for(lista *p=l[1];p!=NULL;p=p->urm)
find(2,p->x,p->x);
}
int main()
{
read();
mns=nmax;
solve();
ofstream g("secv.out");
if(mns==nmax)
mns=-1;
else
++mns;
g<<mns;
}