Submission #59936

#	Time	Username	Problem	Language	Result	Execution time	Memory
59936		Eae02	Circle selection (APIO18_circle_selection)	C++14	0 / 100	3049 ms	65472 KiB

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;
	}
	
	bool intersects(const Circle& other) const
	{
		int64_t dx = x - other.x;
		int64_t dy = y - other.y;
		int64_t rSum = r + other.r;
		return dx * dx + dy * dy <= rSum * rSum;
	}
};

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;
	int64_t sameRad = -1;
	
	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 (i == 0)
			sameRad = circles[i].r;
		else if (sameRad != circles[i].r)
			sameRad = -1;
		
		if (circles[i].y != 0)
			allZeroY = false;
	}
	
	if (sameRad != -1)
	{
		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 if (sameRad != -1)
	{
		std::map<int64_t, std::vector<Circle*>> rows;
		
		for (Circle& circle : circles)
		{
			auto it = rows.find(circle.y);
			if (it != rows.end())
			{
				it->second.push_back(&circle);
			}
			else
			{
				rows.insert(std::make_pair(circle.y, std::vector<Circle*> { &circle }));
			}
		}
		
		for (auto& row : rows)
		{
			std::sort(ALL(row.second), [&] (const Circle* a, const Circle* b) { return a->x < b->x; });
		}
		
		for (Circle& outer : circles)
		{
			if (outer.elimBy != -1)
				continue;
			outer.elimBy = outer.i;
			int64_t minR = outer.y - sameRad * 2;
			int64_t maxR = outer.y + sameRad * 2;
			
			auto rowB = rows.lower_bound(minR);
			auto rowE = rows.upper_bound(maxR + 1);
			
			for (auto it = rowB; it != rowE; ++it)
			{
				int64_t dy = it->first - outer.y;
				int64_t dx = std::ceil(std::sqrt(4 * sameRad * sameRad - dy * dy));
				
				int64_t minX = outer.x - dx;
				int64_t maxX = outer.x + dx;
				
				auto xB = std::lower_bound(ALL(it->second), minX, [&] (const Circle* c, int64_t x) { return c->x < x; });
				auto xE = std::upper_bound(ALL(it->second), maxX, [&] (int64_t x, const Circle* c) { return x < c->x; });
				
				std::for_each(xB, xE, [&](Circle* c)
				{
					if (c->elimBy == -1 && c->intersects(outer))
						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 && inner.intersects(outer))
					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: 0 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13