답안 #59928 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59928	2018-07-23T10:17:15 Z	Eae02	원 고르기 (APIO18_circle_selection)	C++14	19 / 100	3000 ms	37644 KB

circle_selection

#include <bits/stdc++.h>
#define ALL(x) x.begin(),x.end()

struct Circle
{
	int64_t x;
	int64_t y;
	int64_t r;
	int64_t i;
	int64_t elimBy;
	
	int64_t minX() const
	{
		return x - r;
	}
	int64_t maxX() const
	{
		return x + r;
	}
};

int main()
{
	int num;
	std::cin >> num;
	std::vector<Circle> circles(num);
	std::vector<Circle*> cByMin(num);
	std::vector<Circle*> cByMax(num);
	
	bool allZeroY = true;
	
	for (int i = 0; i < num; i++)
	{
		std::cin >> circles[i].x;
		std::cin >> circles[i].y;
		std::cin >> circles[i].r;
		circles[i].i = i;
		circles[i].elimBy = -1;
		cByMin[i] = &circles[i];
		cByMax[i] = &circles[i];
		
		if (circles[i].y != 0)
			allZeroY = false;
	}
	
	std::sort(ALL(circles), [&] (const Circle& a, const Circle& b)
	{
		if (a.r == b.r)
			return a.i < b.i;
		return a.r > b.r;
	});
	
	if (allZeroY)
	{
		std::sort(ALL(cByMin), [&] (const Circle* a, const Circle* b)
		{
			return a->minX() < b->minX();
		});
		
		std::sort(ALL(cByMax), [&] (const Circle* a, const Circle* b)
		{
			return a->maxX() < b->maxX();
		});
		
		for (Circle& outer : circles)
		{
			if (outer.elimBy != -1)
				continue;
			outer.elimBy = outer.i;
			
			auto minB = std::lower_bound(ALL(cByMin), outer.minX(), [&] (Circle* c, int64_t pos) { return c->minX() < pos; });
			auto minE = std::upper_bound(ALL(cByMin), outer.maxX(), [&] (int64_t pos, Circle* c) { return pos < c->minX(); });
			
			auto maxB = std::lower_bound(ALL(cByMax), outer.minX(), [&] (Circle* c, int64_t pos) { return c->maxX() < pos; });
			auto maxE = std::upper_bound(ALL(cByMax), outer.maxX(), [&] (int64_t pos, Circle* c) { return pos <= c->maxX(); });
			
			std::for_each(minB, minE, [&] (Circle* c)
			{
				if (c->elimBy == -1)
					c->elimBy = outer.i;
			});
			std::for_each(maxB, maxE, [&] (Circle* c)
			{
				if (c->elimBy == -1)
					c->elimBy = outer.i;
			});
		}
	}
	else
	{
		for (Circle& outer : circles)
		{
			if (outer.elimBy != -1)
				continue;
			outer.elimBy = outer.i;
			for (Circle& inner : circles)
			{
				if (inner.elimBy != -1)
					continue;
				int64_t dx = inner.x - outer.x;
				int64_t dy = inner.y - outer.y;
				int64_t rSum = inner.r + outer.r;
				if (dx * dx + dy * dy <= rSum * rSum)
					inner.elimBy = outer.i;
			}
		}
	}
	
	std::vector<int64_t> result(num);
	for (int i = 0; i < num; i++)
		result[circles[i].i] = circles[i].elimBy + 1;
	for (int i = 0; i < num; i++)
		std::cout << result[i] << " ";
	std::cout << std::endl;
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	3 ms	356 KB	Output is correct
3	Correct	2 ms	488 KB	Output is correct
4	Correct	3 ms	488 KB	Output is correct
5	Correct	3 ms	488 KB	Output is correct
6	Correct	3 ms	516 KB	Output is correct
7	Correct	3 ms	516 KB	Output is correct
8	Correct	3 ms	516 KB	Output is correct
9	Correct	1 ms	552 KB	Output is correct
10	Correct	3 ms	552 KB	Output is correct
11	Correct	3 ms	560 KB	Output is correct
12	Correct	4 ms	568 KB	Output is correct
13	Correct	3 ms	568 KB	Output is correct
14	Correct	3 ms	568 KB	Output is correct
15	Correct	3 ms	576 KB	Output is correct
16	Correct	5 ms	700 KB	Output is correct
17	Correct	7 ms	768 KB	Output is correct
18	Correct	6 ms	768 KB	Output is correct
19	Correct	14 ms	1136 KB	Output is correct
20	Correct	20 ms	1416 KB	Output is correct
21	Correct	14 ms	1500 KB	Output is correct
22	Correct	68 ms	1656 KB	Output is correct
23	Correct	67 ms	1836 KB	Output is correct
24	Correct	60 ms	2012 KB	Output is correct
25	Correct	53 ms	2076 KB	Output is correct
26	Correct	60 ms	2224 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	786 ms	22736 KB	Output is correct
2	Correct	757 ms	22740 KB	Output is correct
3	Correct	778 ms	22740 KB	Output is correct
4	Correct	675 ms	22740 KB	Output is correct
5	Correct	609 ms	22740 KB	Output is correct
6	Correct	825 ms	27424 KB	Output is correct
7	Correct	673 ms	32212 KB	Output is correct
8	Correct	610 ms	36844 KB	Output is correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	36844 KB	Output is correct
2	Execution timed out	3036 ms	36844 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	3066 ms	36844 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	3 ms	356 KB	Output is correct
3	Correct	2 ms	488 KB	Output is correct
4	Correct	3 ms	488 KB	Output is correct
5	Correct	3 ms	488 KB	Output is correct
6	Correct	3 ms	516 KB	Output is correct
7	Correct	3 ms	516 KB	Output is correct
8	Correct	3 ms	516 KB	Output is correct
9	Correct	1 ms	552 KB	Output is correct
10	Correct	3 ms	552 KB	Output is correct
11	Correct	3 ms	560 KB	Output is correct
12	Correct	4 ms	568 KB	Output is correct
13	Correct	3 ms	568 KB	Output is correct
14	Correct	3 ms	568 KB	Output is correct
15	Correct	3 ms	576 KB	Output is correct
16	Correct	5 ms	700 KB	Output is correct
17	Correct	7 ms	768 KB	Output is correct
18	Correct	6 ms	768 KB	Output is correct
19	Correct	14 ms	1136 KB	Output is correct
20	Correct	20 ms	1416 KB	Output is correct
21	Correct	14 ms	1500 KB	Output is correct
22	Correct	68 ms	1656 KB	Output is correct
23	Correct	67 ms	1836 KB	Output is correct
24	Correct	60 ms	2012 KB	Output is correct
25	Correct	53 ms	2076 KB	Output is correct
26	Correct	60 ms	2224 KB	Output is correct
27	Correct	22 ms	36844 KB	Output is correct
28	Correct	20 ms	36844 KB	Output is correct
29	Correct	22 ms	36844 KB	Output is correct
30	Correct	212 ms	36844 KB	Output is correct
31	Correct	213 ms	36844 KB	Output is correct
32	Correct	222 ms	36844 KB	Output is correct
33	Correct	219 ms	36844 KB	Output is correct
34	Correct	199 ms	36844 KB	Output is correct
35	Correct	253 ms	36844 KB	Output is correct
36	Execution timed out	3045 ms	37644 KB	Time limit exceeded
37	Halted	0 ms	0 KB	-

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	3 ms	356 KB	Output is correct
3	Correct	2 ms	488 KB	Output is correct
4	Correct	3 ms	488 KB	Output is correct
5	Correct	3 ms	488 KB	Output is correct
6	Correct	3 ms	516 KB	Output is correct
7	Correct	3 ms	516 KB	Output is correct
8	Correct	3 ms	516 KB	Output is correct
9	Correct	1 ms	552 KB	Output is correct
10	Correct	3 ms	552 KB	Output is correct
11	Correct	3 ms	560 KB	Output is correct
12	Correct	4 ms	568 KB	Output is correct
13	Correct	3 ms	568 KB	Output is correct
14	Correct	3 ms	568 KB	Output is correct
15	Correct	3 ms	576 KB	Output is correct
16	Correct	5 ms	700 KB	Output is correct
17	Correct	7 ms	768 KB	Output is correct
18	Correct	6 ms	768 KB	Output is correct
19	Correct	14 ms	1136 KB	Output is correct
20	Correct	20 ms	1416 KB	Output is correct
21	Correct	14 ms	1500 KB	Output is correct
22	Correct	68 ms	1656 KB	Output is correct
23	Correct	67 ms	1836 KB	Output is correct
24	Correct	60 ms	2012 KB	Output is correct
25	Correct	53 ms	2076 KB	Output is correct
26	Correct	60 ms	2224 KB	Output is correct
27	Correct	786 ms	22736 KB	Output is correct
28	Correct	757 ms	22740 KB	Output is correct
29	Correct	778 ms	22740 KB	Output is correct
30	Correct	675 ms	22740 KB	Output is correct
31	Correct	609 ms	22740 KB	Output is correct
32	Correct	825 ms	27424 KB	Output is correct
33	Correct	673 ms	32212 KB	Output is correct
34	Correct	610 ms	36844 KB	Output is correct
35	Correct	2 ms	36844 KB	Output is correct
36	Execution timed out	3036 ms	36844 KB	Time limit exceeded
37	Halted	0 ms	0 KB	-

답안 #59928

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 12.0 / 12.0

Subtask #3 0 / 15.0

Subtask #4 0 / 23.0

Subtask #5 0 / 30.0

Subtask #6 0 / 13.0

Subtask #1
7.0 / 7.0

Subtask #2
12.0 / 12.0

Subtask #3
0 / 15.0

Subtask #4
0 / 23.0

Subtask #5
0 / 30.0

Subtask #6
0 / 13.0