Cod sursa(job #2927416)

Utilizator cezarinfoTulceanu Cezar cezarinfo Data 20 octombrie 2022 14:22:39
Problema Secv Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
FILE*in=fopen("secv.in","r");
FILE*out=fopen("secv.out","w");
const int NMAX=5007,INF=2000000007;
int n,i,v[NMAX],lmin=INF,el,use;
bool as=0;
vector<int> w;
map<int,bool> m;
map<int,int> nex;
map<int,queue<int> > mq;
int nx[NMAX];
int main()
{
    fscanf(in,"%d",&n);
    if(n==0)
    {
        fprintf(out,"0");
        return 0;
    }
    for(i=1;i<=n;i++)
    {
        fscanf(in,"%d",&v[i]);
        if(m[v[i]]==0)
        {
            w.push_back(v[i]);
            m[v[i]]=1;
        }
    }
    sort(w.begin(),w.end());
    for(int it=0;it<w.size()-1;it++)
    {
        nex[w[it]]=w[it+1];
    }
    for(i=1;i<=n;i++)
    {
        while(!mq[v[i]].empty())
        {
            nx[mq[v[i]].front()]=i;
            mq[v[i]].pop();
        }
        if(nex[v[i]]!=0)
        {
            mq[nex[v[i]]].push(i);
        }
    }
    for(i=1;i<=n;i++)
    {
        el=i;
        if(v[i]==w[0])
        {
            while(nx[el]!=0)
            {
                el=nx[el];
            }
            if(v[el]==w[w.size()-1])
            {
                as=1;
                use=el-i+1;
                lmin=min(lmin,use);
            }
        }
    }
    if(as==0)
    {
        fprintf(out,"-1");
        return 0;
    }
    fprintf(out,"%d",lmin);
    return 0;
}