Untitled

#define MAX_N           200
#define MAX_BACTERIA    3001
#define DIST(a, b)      (a > b ? a - b : b - a)

struct Result
{
	int row, col;
};

struct Bacteria
{
	int id, size, time;
};

int N, map[MAX_N + 2][MAX_N + 2], dead_time[MAX_BACTERIA];
int visit[MAX_N + 2][MAX_N + 2], base;
int heap_size, heap[MAX_N * MAX_N];

void heap_push(int value)
{
	heap[heap_size] = value;
	register int current = heap_size, parent = (current - 1) / 2;
	while (current > 0 && heap[current] < heap[parent])
	{
		int temp = heap[parent];
		heap[parent] = heap[current];
		heap[current] = temp;
		current = parent;
		parent = (current - 1) / 2;
	}
	heap_size++;
}

int heap_pop(void)
{
	int ret = heap[0];
	heap[0] = heap[--heap_size];
	register int current = 0, lchild = current * 2 + 1;
	while (lchild < heap_size)
	{
		int child;
		if (lchild + 1 == heap_size)
			child = lchild;
		else
			child = heap[lchild] < heap[lchild + 1] ? lchild : lchild + 1;
		if (heap[current] < heap[child])
			break;
		int temp = heap[current];
		heap[current] = heap[child];
		heap[child] = temp;
		current = child;
		lchild = current * 2 + 1;
	}
	return ret;
}

void init(int N)
{
	::N = N;
	dead_time[MAX_BACTERIA] = 200000;
	for (register int i = 0; i < N + 2; i++)
		map[0][i] = map[N + 1][i] = map[i][0] = map[i][N + 1] = MAX_BACTERIA;
	for (register int i = 1; i <= N; i++)
		for (register int j = 1; j <= N; j++)
			map[i][j] = 0;
}

Result putBacteria(int mTime, int mRow, int mCol, Bacteria mBac)
{
	Result ret;
	if (dead_time[map[mRow][mCol]] > mTime)
	{
		ret.col = 0;
		ret.row = 0;
		return ret;
	}

	base++;
	heap_size = 0;

	int cur = (mRow << 8) | mCol;
	dead_time[mBac.id] = mTime + mBac.time;

	visit[mRow][mCol] = base;
	heap_push(cur);

	while (heap_size)
	{
		cur = heap_pop();
		int cur_r = (cur >> 8) & 0xFF;
		int cur_c = cur & 0xFF;
		map[cur_r][cur_c] = mBac.id;

		if (--mBac.size == 0)
		{
			ret.col = cur_c;
			ret.row = cur_r;
			return ret;
		}
		for (register int i = 0; i < 4; i++)
		{
			const int dr[4] = { -1, 0, 0, 1 };
			const int dc[4] = { 0, -1, 1, 0 };

			int next_r = cur_r + dr[i];
			int next_c = cur_c + dc[i];

			if (next_c < 1 || next_c > N) continue;
			if (next_r < 1 || next_r > N) continue;
			if (visit[next_r][next_c] == base || dead_time[map[next_r][next_c]] > mTime)
				continue;

			visit[next_r][next_c] = base;
			int next = ((DIST(next_r, mRow) + DIST(next_c, mCol)) << 16) | (next_r << 8) | next_c;
			heap_push(next);
		}
	}   
	dead_time[mBac.id] = 0;
	{
		ret.col = 0;
		ret.row = 0;
		return ret;
	}
}

int killBacteria(int mTime, int mRow, int mCol)
{
	int id = map[mRow][mCol];
	if (dead_time[id] <= mTime)
		return 0;
	dead_time[id] = mTime;
	return id;
}

int checkCell(int mTime, int mRow, int mCol)
{
	int id = map[mRow][mCol];
	if (dead_time[id] <= mTime)
		return 0;
	return id;
}