3719783_tle.cc

北大大牛代码 1240道题的原代码 超级权威

#include <set>
#include <stdio.h>
#include <algorithm>

using namespace std;

set <int> s;
set <int>::iterator it;
int tmd[500001];
int table[1001];
int ans[1001];

int main()
{
	int t, k, n;
	char str[2];
	int cas = 1;
	int min, max;

	while (scanf("%d", &t) == 1 && t != 0)
	{
		for (int i = 0; i <= 1000; i++)
		{
			table[i] = 500000;
		}
		printf("Case %d:\n", cas++);
		k = 1;
		s.clear();
		min = 5000000;max = 0;
		while (t-- != 0)
		{
			scanf("%s%d", str, &n);
			if (str[0] == 'B')
			{
				s.insert(n);
				if (n < min)	min = n;
				if (n > max)	max = n;
				for (int i = 1; i <= 1000; i++)
				{
					int tmp = n < i ? n : (n % i);
					if (tmp <= table[i])
					{
						table[i] = tmp;
						ans[i] = k;
					}
				}
				tmd[n] = k++;
			}
			else
			{
				if (s.empty())
				{
					puts("-1");
					continue;
				}
				if (n <= 1000)
				{
					printf("%d\n", ans[n]);
					continue;
				}
				int tmp;
				tmp = min - min % k + k; 
				int res = min;
				while ( tmp <= max )
				{
					it = s.lower_bound( tmp );
					if ( *it < tmp + k )
					{
						if ( *it - tmp < res % k || ( *it - tmp == res % k && tmd[*it] > tmd[res] ) )
						{
							res = *it;
						}
						tmp += k;
					}
					else if ( it != s.end() )
					{
						if ( *it % k < res % k || ( *it % k == res % k && tmd[*it] > tmd[res] ) )
						{
							res = *it;
						}
						tmp = *it - *it % k + k;
					}
					else
					{
						break;
					}
				}
				printf("%d\n", tmd[res]);
			}
		}
		puts("");
	}
	return 0;
}