제출 #243455

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
243455		atoiz	원 고르기 (APIO18_circle_selection)	C++14	87 / 100	3078 ms	19560 KiB

circle_selection

// https://oj.uz/submission/77965

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

const int INF = 1000 * 1000 * 1000 + 8;

int64_t sqr(int x) { return (int64_t) x * x; }
void minimize(int &x, int y) { x = (x < y ? x : y); }
void maximize(int &x, int y) { x = (x > y ? x : y); }

struct Box
{
	int x0, x1, y0, y1;
	Box(int _x0 = INF, int _x1 = -INF, int _y0 = INF, int _y1 = -INF): x0(_x0), x1(_x1), y0(_y0), y1(_y1) {}
	bool intersect(const Box &b) const { return (x0 <= b.x1 && b.x0 <= x1 && y0 <= b.y1 && b.y0 <= y1); }
	void expand(const Box &b) { minimize(x0, b.x0), minimize(y0, b.y0), maximize(x1, b.x1), maximize(y1, b.y1); }
};

struct Circle
{
	int x, y, r, i;
	bool intersect(const Circle &c) const { return sqr(c.x - x) + sqr(c.y - y) <= sqr(r + c.r); }
	Box toBox() { return Box(x - r, x + r, y - r, y + r); }
};

bool compX(const Circle &a, const Circle &b) { return (a.x == b.x ? (a.y < b.y) : (a.x < b.x)); }
bool compY(const Circle &a, const Circle &b) { return (a.y == b.y ? (a.x < b.x) : (a.y < b.y)); }
bool compR(const Circle &a, const Circle &b) { return (a.r == b.r ? (a.i < b.i) : (a.r > b.r)); }

int n;
vector<int> ans;
vector<Circle> circles, cirTree;
vector<Box> boxTree;

void build(int lo = 0, int hi = n - 1, bool byX = 0)
{
	int mid = (lo + hi) >> 1;
	nth_element(cirTree.begin() + lo, cirTree.begin() + mid, cirTree.begin() + hi + 1, (byX ? compX : compY));
	boxTree[mid] = cirTree[mid].toBox();

	if (lo < mid) {
		build(lo, mid - 1, !byX);
		boxTree[mid].expand(boxTree[(lo + mid - 1) >> 1]);
	}

	if (mid < hi) {
		build(mid + 1, hi, !byX);
		boxTree[mid].expand(boxTree[(mid + 1 + hi) >> 1]);
	}

	// cout << mid << ' ' << lo << ' ' << hi << ' ' << cirTree[mid].i << ": ";
	// cout << boxTree[mid].x0 << ' ' << boxTree[mid].x1 << ' ' << boxTree[mid].y0 << ' ' << boxTree[mid].y1 << endl;
}

void get(Circle &c, Box &b, int lo = 0, int hi = n - 1, bool byX = 0)
{
	int mid = (lo + hi) >> 1;
	if (ans[cirTree[mid].i] == -1 && cirTree[mid].intersect(c)) ans[cirTree[mid].i] = c.i;
	// cout << c.i << ": " << lo << ' ' << hi << ' ' << cirTree[mid].i << " - ";
	// cout << boxTree[mid].x0 << ' ' << boxTree[mid].x1 << ' ' << boxTree[mid].y0 << ' ' << boxTree[mid].y1 << endl;

	boxTree[mid] = Box(INF, -INF, INF, -INF);
	if (ans[cirTree[mid].i] == -1) boxTree[mid] = cirTree[mid].toBox();
	int lc = (lo + mid - 1) >> 1, rc = (mid + 1 + hi) >> 1;
	if (lo < mid) {
		if (boxTree[lc].intersect(b)) get(c, b, lo, mid - 1, !byX);
		boxTree[mid].expand(boxTree[lc]);
	}
	if (mid < hi) {
		if (boxTree[rc].intersect(b)) get(c, b, mid + 1, hi, !byX);
		boxTree[mid].expand(boxTree[rc]);
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	circles.resize(n);
	for (int i = 0; i < n; ++i) {
		cin >> circles[i].x >> circles[i].y >> circles[i].r;
		circles[i].i = i;
	}
	sort(circles.begin(), circles.end(), compR);

	cirTree = circles;
	boxTree.resize(n);
	ans.assign(n, -1);
	build();

	for (auto &c : circles) if (ans[c.i] == -1) {
		ans[c.i] = c.i;
		Box b = c.toBox();
		get(c, b);
	}
	for (int i = 0; i < n; ++i) cout << ans[i] + 1 << ' ';
}

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