代码

#include <algorithm>

int query_kth(const int *A, int na, const int *B, int nb, const int *C, int nc, int k)
{
	const int *value[3] = {A, B, C};
	int l[3] = {0, 0, 0}, r[3] = {na, nb, nc}, mid[3] = {na + 1 >> 1, nb + 1 >> 1, nc + 1 >> 1};
	int size(3), o[3] = {0, 1, 2}, x[3] = {value[0][mid[0]], value[1][mid[1]], value[2][mid[2]]};
	while (true)
	{
		if (size == 1 && k == mid[0] + mid[1] + mid[2] + 1)
			return x[*o];
		if (k <= mid[0] + mid[1] + mid[2] + 1)
		{
			if (size > 1 && x[*o] < x[o[1]])
				std::swap(*o, o[1]);
			if (size > 2 && x[*o] < x[o[2]])
				std::swap(*o, o[2]);
			r[*o] = mid[*o] - 1;
		}
		else
		{
			if (size > 1 && x[*o] > x[o[1]])
				std::swap(*o, o[1]);
			if (size > 2 && x[o[0]] > x[o[2]])
				std::swap(*o, o[2]);
			l[*o] = mid[*o] + 1;
		}
		mid[*o] = l[*o] + r[*o] + 1 >> 1;
		if (l[*o] <= r[*o])
			x[*o] = value[*o][mid[*o]];
		else
			std::swap(*o, o[--size]);
	}
}

评测结果