4054789_ac_3172ms_1412k.cc

来自「北大大牛代码 1240道题的原代码 超级权威」· CC 代码 · 共 74 行

#include <stdio.h>
#include <ext/hash_map>

using namespace std;
using namespace __gnu_cxx;

#define BASE 10000019

struct Range
{
	int *start, *end;
	size_t h;
};

struct Equal
{
	bool operator ()(const Range &a, const Range &b)	const
	{
		return a.h == b.h && equal(a.start, a.end, b.start);
	}
};

struct Hash
{
	size_t operator ()(const Range &a)	const
	{
		return a.h;
	}
};

int main()
{
	int n, k, high;
	bool found;

	scanf("%d%d", &n, &k);
	int data[n];
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &data[i]);
	}
	int min, max, mid;
	min = 1; max = n;
	double st = clock();
	while (min < max - 1)
	{
		hash_map <Range, int, Hash, Equal> h;
		high = 1;
		mid = (min + max) >> 1;
		Range range = {data, data + mid, 0};
		found = false;

		for (int i = 0; i < mid; i++)
		{
			range.h = range.h * BASE + data[i];
			high *= BASE;
		}
		for (int i = 0; i + mid <= n; i++)
		{
			if (++h[range] >= k)
			{
				found = true;
				break;
			}
			range.h = range.h * BASE + data[i + mid] - high * data[i];
			range.start++;
			range.end++;
		}
		found ? min = mid : max = mid;
	}
	printf("%d\n", min);
	return 0;
}