3719081_tle.cpp

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

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

using namespace std;

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

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

	while (scanf("%d", &t) == 1 && t != 0)
	{
		for (int i = 0; i <= 800; i++)
		{
			table[i] = 500000;
		}
		printf("Case %d:\n", cas++);
		k = 1;
		s.clear();
		while (t-- != 0)
		{
			scanf("%s%d", str, &n);
			if (str[0] == 'B')
			{
				s.insert(n);
				for (int i = 1; i <= 800; i++)
				{
					if (n % i <= table[i])
					{
						table[i] = n % i;
						ans[i] = k;
					}
				}
				tmd[n] = k++;
			}
			else
			{
				if (s.empty())
				{
					puts("-1");
					continue;
				}
				if (n <= 800)
				{
					printf("%d\n", ans[n]);
					continue;
				}
				r = 500000;g = 0;
				int tmp = 0;
				int c;
				for (c = 0, it = s.begin(); it != s.end(); ++it, c++)
				{
					num[c] = (*it);
				}
				int min = 0, max, mid;
				while (true)
				{
					max = c;
					while (min < max)
					{
						mid = (min + max) >> 1;
						if (num[mid] <= tmp)
							min = mid + 1;
						else
							max = mid;
					}
					if (min >= c)
						break;
					int nd = num[min];
					int tn = nd % n;
					if (tn < r || (tn == r && tmd[nd] > g))
					{
						r = tn;
						g = tmd[nd];
					}
					tmp = (nd / n + 1 ) * n;
				}
				printf("%d\n", g);
			}
		}
		puts("");
	}
	return 0;
}