Cod sursa(job #465122)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 23 iunie 2010 13:01:11
Problema Secv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>

using namespace std;

#define file_in "secv.in"
#define file_out "secv.out"

#define nmax (1<<14)

int n;
vector<int> v,s;
int p[201000100];
int x[nmax];

void citire()
{
    int x;
    freopen(file_in,"r",stdin);
    freopen(file_out,"w",stdout);

    scanf("%d", &n);
    for (int i=0;i<n;++i)
    {
        scanf("%d", &x);

        v.push_back(x);
        s.push_back(x);
    }

}

#define inf 0x3f3f3f3f

void solve()
{
    int i,nr;
    int sol;

     sort(v.begin(),v.end());
     nr=1;
     p[v[0]]=1;
     for (i=1;i<n;++i)
          if (v[i]!=v[i-1])
          {
              ++nr;
              p[v[i]]=nr;
          }
     for (i=1;i<=nr;++i)
          x[i]=-inf;
     sol=inf;
     for (i=0;i<=n;++i)
     {
        if (p[s[i]]==1)
        x[1]=i;
        else
        x[p[s[i]]]=x[p[s[i]]-1];
        sol=min(sol,i-x[nr]);
     }

     if (sol==inf)
         printf("-1\n");
     else
         printf("%d\n", sol+1);
}

int main()
{
    citire();
    solve();

    fclose(stdin);
    fclose(stdout);

    return 0;
}