제출 #243421

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

circle_selection

/*input
11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1
*/

// spoiled

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

using namespace std;

inline long long sqr(int x) { return (long long) x * x; }

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);
	}
};

const int OFFSET = 1000 * 1000 * 1000;
int N;
vector<Circle> cir;
vector<int> ans;
unordered_map<int, unordered_map<int, vector<int>>> grid;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	ans.assign(N, -1);
	cir.resize(N);
	for (int i = 0; i < N; ++i) {
		cin >> cir[i].x >> cir[i].y >> cir[i].r;
		cir[i].x += OFFSET;
		cir[i].y += OFFSET;
		cir[i].i = i;
	}

	auto vec = cir;
	sort(vec.begin(), vec.end(), [&](Circle &a, Circle &b) {
		return (a.r == b.r ? (a.i < b.i) : (a.r > b.r));
	});

	auto c = vec.begin();
	for (int i = 30; i >= 0; --i) {
		grid.clear();
		for (auto t : vec) if (!~ans[t.i]) {
			grid[t.x >> i][t.y >> i].push_back(t.i);
		}

		for (; c != vec.end() && c->r > ((1 << i) >> 1); ++c) if (!~ans[c->i]) {
			int cx = c->x >> i, cy = c->y >> i;
			for (int tx = cx - 2; tx <= cx + 2; ++tx) {
				for (int ty = cy - 2; ty <= cy + 2; ++ty) {
					vector<int> &cur = grid[tx][ty], tmp;
					if (cur.empty()) continue;
					for (int id : cur) {
						if (c->intersect(cir[id])) {
							ans[id] = c->i;
						} else {
							tmp.push_back(id);
						}
					}
					cur = move(tmp);
				}
			}
		}
	}

	for (int i = 0; i < N; ++i) cout << ans[i] + 1 << ' ';
}

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