KOIREP.cpp

#include<stdio.h>

typedef struct{
	int group;
	int ability;
}Person;

Person person[1000005];
int leng;
int cnt[1000];

// Sắp xếp trộn 
void Merge(Person *p, int left, int m, int right)
{
	int l = left, r = m + 1, k = 0;
	Person *temp = new Person[right - left + 1];

	while(l <= m && r <= right)
	{
		if(p[l].ability < p[r].ability) temp[k++] = p[l++];
		else temp[k++] = p[r++];
	}

	while(l <= m) temp[k++] = p[l++];
	while(r <= right) temp[k++] = p[r++];

	for(int i = 0; i < k; i++)
		p[i+left] = temp[i];
	delete[] temp;
}

void MergeSort(Person *p, int left, int right)
{
	int m;
	if(left < right)
	{
		m = (left + right)/2;
		MergeSort(p,left,m);
		MergeSort(p,m+1,right);
		Merge(p,left,m,right);
	}
}

int main()
{
	int n,m,t;
	scanf("%d%d",&n,&m);
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
		{
			scanf("%d",&t);
			person[leng].group = i;
			person[leng].ability = t;
			leng++;
		}
		
	MergeSort(person, 0, leng-1);
	
	for(int i = 0; i < n; i++)
		cnt[i] = 0;

	int num_group = 0;
	int l = 0, r = 0;
	int _min = 1000000005;

	while(r < n*m)
	{
		int pos = person[r].group;
		if(num_group < n)
		{	
			if(cnt[pos] == 0) num_group++;
			cnt[pos]++;
			r++;
		}
		else 
		{
			while(num_group >= n)
			{
				int t = person[l].group;
				cnt[t]--;
				if(cnt[t] == 0) num_group--;
				l++;
			}
			int temp = person[r-1].ability - person[l-1].ability;
			if(temp < _min) _min = temp;
		}
	}
	printf("%d\n",_min);
	return 0;
}