oj.uz

Submission #122854

# Submission time Handle Problem Language Result Execution time Memory
122854 2019-06-29T11:22:23 Z diamond_duke Circle selection (APIO18_circle_selection) C++11
7 / 100
 3000 ms 34040 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7544 KB Output is correct
2 Correct 8 ms 7412 KB Output is correct
3 Correct 7 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 8 ms 7400 KB Output is correct
6 Correct 8 ms 7416 KB Output is correct
7 Correct 8 ms 7416 KB Output is correct
8 Correct 8 ms 7420 KB Output is correct
9 Correct 8 ms 7396 KB Output is correct
10 Correct 8 ms 7416 KB Output is correct
11 Correct 8 ms 7416 KB Output is correct
12 Correct 8 ms 7388 KB Output is correct
13 Correct 8 ms 7420 KB Output is correct
14 Correct 8 ms 7416 KB Output is correct
15 Correct 8 ms 7416 KB Output is correct
16 Correct 9 ms 7416 KB Output is correct
17 Correct 10 ms 7416 KB Output is correct
18 Correct 10 ms 7416 KB Output is correct
19 Correct 13 ms 7800 KB Output is correct
20 Correct 12 ms 7672 KB Output is correct
21 Correct 12 ms 7800 KB Output is correct
22 Correct 1262 ms 7872 KB Output is correct
23 Correct 1373 ms 7928 KB Output is correct
24 Correct 1230 ms 7928 KB Output is correct
25 Correct 1327 ms 7928 KB Output is correct
26 Correct 1238 ms 7928 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 26976 KB Output is correct
2 Correct 248 ms 27164 KB Output is correct
3 Correct 246 ms 26716 KB Output is correct
4 Correct 237 ms 26988 KB Output is correct
5 Execution timed out 3060 ms 23560 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Execution timed out 3032 ms 16384 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3050 ms 34040 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7544 KB Output is correct
2 Correct 8 ms 7412 KB Output is correct
3 Correct 7 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 8 ms 7400 KB Output is correct
6 Correct 8 ms 7416 KB Output is correct
7 Correct 8 ms 7416 KB Output is correct
8 Correct 8 ms 7420 KB Output is correct
9 Correct 8 ms 7396 KB Output is correct
10 Correct 8 ms 7416 KB Output is correct
11 Correct 8 ms 7416 KB Output is correct
12 Correct 8 ms 7388 KB Output is correct
13 Correct 8 ms 7420 KB Output is correct
14 Correct 8 ms 7416 KB Output is correct
15 Correct 8 ms 7416 KB Output is correct
16 Correct 9 ms 7416 KB Output is correct
17 Correct 10 ms 7416 KB Output is correct
18 Correct 10 ms 7416 KB Output is correct
19 Correct 13 ms 7800 KB Output is correct
20 Correct 12 ms 7672 KB Output is correct
21 Correct 12 ms 7800 KB Output is correct
22 Correct 1262 ms 7872 KB Output is correct
23 Correct 1373 ms 7928 KB Output is correct
24 Correct 1230 ms 7928 KB Output is correct
25 Correct 1327 ms 7928 KB Output is correct
26 Correct 1238 ms 7928 KB Output is correct
27 Correct 16 ms 8060 KB Output is correct
28 Correct 16 ms 8188 KB Output is correct
29 Correct 16 ms 8184 KB Output is correct
30 Execution timed out 3055 ms 8316 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7544 KB Output is correct
2 Correct 8 ms 7412 KB Output is correct
3 Correct 7 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 8 ms 7400 KB Output is correct
6 Correct 8 ms 7416 KB Output is correct
7 Correct 8 ms 7416 KB Output is correct
8 Correct 8 ms 7420 KB Output is correct
9 Correct 8 ms 7396 KB Output is correct
10 Correct 8 ms 7416 KB Output is correct
11 Correct 8 ms 7416 KB Output is correct
12 Correct 8 ms 7388 KB Output is correct
13 Correct 8 ms 7420 KB Output is correct
14 Correct 8 ms 7416 KB Output is correct
15 Correct 8 ms 7416 KB Output is correct
16 Correct 9 ms 7416 KB Output is correct
17 Correct 10 ms 7416 KB Output is correct
18 Correct 10 ms 7416 KB Output is correct
19 Correct 13 ms 7800 KB Output is correct
20 Correct 12 ms 7672 KB Output is correct
21 Correct 12 ms 7800 KB Output is correct
22 Correct 1262 ms 7872 KB Output is correct
23 Correct 1373 ms 7928 KB Output is correct
24 Correct 1230 ms 7928 KB Output is correct
25 Correct 1327 ms 7928 KB Output is correct
26 Correct 1238 ms 7928 KB Output is correct
27 Correct 235 ms 26976 KB Output is correct
28 Correct 248 ms 27164 KB Output is correct
29 Correct 246 ms 26716 KB Output is correct
30 Correct 237 ms 26988 KB Output is correct
31 Execution timed out 3060 ms 23560 KB Time limit exceeded
32 Halted 0 ms 0 KB -