Cod sursa(job #272929)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 7 martie 2009 23:02:01
Problema Secv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
FILE*fin=fopen("secv.in","r");
FILE*fout=fopen("secv.out","w");
#define nm 5005
#define pb push_back
int n,a[nm],bst[nm];
vector<int> b,c;
int main()
{
    int i,j,m,ans=10000,p,mid,ec,st,dr;
    fscanf(fin,"%d",&n);
    for(i=1;i<=n;i++)
    {
      fscanf(fin,"%d",&a[i]);
      b.pb(a[i]);
    }  
    sort(b.begin(),b.end());
    i=0;
    b.pb(b[n-1]);
    while(i<n)
    {
      while(i<n&&b[i]==b[i+1]) i++;
      c.pb(b[i]);
      i++;
    }
    m=c.size();
    for(i=0;i<m;i++)
      bst[i]=0;
    for(i=1;i<=n;i++)
    {
      ec=a[i];
      st=0;dr=m-1;
      while(st<dr)
      {
        mid=(st+dr)/2;
        if(c[mid]==ec)
        {
          st=dr=mid;
          break;
        }
        if(c[mid]<ec) st=mid+1;
        else dr=mid-1;
      }
      p=st;
      if(p==0) bst[p]=i;
      else bst[p]=bst[p-1];
      if(p==m-1&&bst[p]) if(i-bst[p]+1<ans) ans=i-bst[p]+1;
    }
    if(ans==10000) fprintf(fout,"-1\n");
    else fprintf(fout,"%d\n",ans);
    fclose(fin);
    fclose(fout);
    return 0;
}