Cod sursa(job #2986724)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 28 februarie 2023 23:16:30
Problema Secv Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
//Ilie Dumitru
#include<cstdio>
#include<vector>
#include<algorithm>
const int NMAX=5005;

struct membru
{
	int x;
};

int N, M;
int v[NMAX], compressed[NMAX];
std::vector<int> app[NMAX];
int used[NMAX];

int binarySearchForCompression(int x)
{
	int l=-1, r=M, m;
	while(r-l>1)
	{
		m=(l+r)/2;
		if(compressed[m]<=x)
			l=m;
		else
			r=m;
	}
	return l;
}

int main()
{
	FILE* f=fopen("secv.in", "r"), *g=fopen("secv.out", "w");
	int i, min=NMAX;

	fscanf(f, "%d", &N);
	for(i=0;i<N;++i)
		fscanf(f, "%d", v+i), compressed[i]=v[i];
	std::sort(compressed, compressed+N);

	for(i=1;i<N;++i)
		if(compressed[i]!=compressed[M])
			compressed[++M]=compressed[i];
	++M;

	for(i=0;i<N;++i)
	{
		v[i]=binarySearchForCompression(v[i]);
		app[v[i]].push_back(i);
	}

	for(i=1;i<M;++i)
	{
		while(used[i]<(int)app[i].size() && app[i][used[i]]<app[i-1][used[i-1]])
			++used[i];
		if(used[i]==(int)app[i].size())
			used[0]=app[0].size(), i=M;
	}

	for(;used[0]<(int)app[0].size();++used[0])
	{
		for(i=1;i<M && app[i][used[i]]<app[i-1][used[i-1]];++i)
		{
			while(used[i]<(int)app[i].size() && app[i][used[i]]<app[i-1][used[i-1]])
				++used[i];
			if(used[i]==(int)app[i].size())
				used[0]=app[0].size(), i=M;
		}
		if(used[0]<(int)app[0].size())
		{
			if(app[M-1][used[M-1]]-app[0][used[0]]<min)
				min=app[M-1][used[M-1]]-app[0][used[0]];
		}
	}

	fprintf(g, "%d\n", min==NMAX?-1:min+1);

	fclose(f);
	fclose(g);
	return 0;
}