Submission #122860

#	Time	Username	Problem	Language	Result	Execution time	Memory
122860		diamond_duke	Circle selection (APIO18_circle_selection)	C++11	100 / 100	1285 ms	37064 KiB

circle_selection

#include <algorithm>
#include <cstdio>
#include <vector>
using ll = long long;
inline ll sqr(ll x) { return x * x; }
struct circle { int x, y, r; } arr[300005], val[300005];
bool operator <(circle a, circle b)
{
	if (a.x == b.x)
		return a.y < b.y;
	return a.x < b.x;
}
bool intersect(circle a, circle b) { return sqr(a.x - b.x) + sqr(a.y - b.y) <= sqr(a.r + b.r); }
int seq[300005], ans[300005];
std::vector<int> vec[300005];
int main()
{
	int n, rad = 0, len = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d%d%d", &arr[i].x, &arr[i].y, &arr[i].r);
		arr[i].x += 1e9;
		arr[i].y += 1e9;
		seq[i] = i;
		ans[i] = -1;
	}
	std::sort(seq, seq + n, [&] (int x, int y)
	{
		if (arr[x].r == arr[y].r)
			return x < y;
		return arr[x].r > arr[y].r;
	});
	auto resize = [&] ()
	{
		int cnt = 0;
		for (int i = 0; i < n; i++)
		{
			if (-1 == ans[i])
				val[cnt++] = {arr[i].x / rad, arr[i].y / rad, i};
		}
		std::sort(val, val + cnt);
		len = 0;
		for (int l = 0, r = 0; l < cnt; l = r)
		{
			while (r < cnt && val[l].x == val[r].x && val[l].y == val[r].y)
				r++;
			vec[len].clear();
			for (int i = l; i < r; i++)
				vec[len].push_back(val[i].r);
			val[len++] = val[l];
		}
	};
	for (int i = 0; i < n; i++)
	{
		int u = seq[i];
		if (~ans[u])
			continue;
		if (!rad || rad / 2 > arr[u].r)
		{
			rad = arr[u].r;
			resize();
		}
		int x = arr[u].x / rad, y = arr[u].y / rad;
		for (int xx = x - 2; xx <= x + 2; xx++)
		{
			for (int yy = y - 2; yy <= y + 2; yy++)
			{
				circle cur = {xx, yy, -1};
				int pos = std::lower_bound(val, val + len, cur) - val;
				if (pos >= len || val[pos].x != xx || val[pos].y != yy)
					continue;
				std::vector<int> nxt;
				for (int v : vec[pos])
				{
					if (intersect(arr[u], arr[v]))
						ans[v] = u;
					else
						nxt.push_back(v);
				}
				vec[pos] = nxt;
			}
		}
	}
	for (int i = 0; i < n; i++)
		printf("%d%c", ans[i] + 1, " \n"[i + 1 == n]);
	return 0;
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
circle_selection.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &arr[i].x, &arr[i].y, &arr[i].r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 30 / 30
• Subtask 6: 13 / 13