Submission #243434

#	Time	Username	Problem	Language	Result	Execution time	Memory
243434		atoiz	Circle selection (APIO18_circle_selection)	C++14	100 / 100	1120 ms	48156 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 <ctime>
#include <random>
#include <chrono>
#include <unordered_map>

using namespace std;

mt19937 rng(/*chrono::system_clock().now().time_since_epoch().count()*/100);

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<long long, vector<int>> grid;

inline long long hsh(int x, int y) { return (((long long) x) << 30 ^ y); }

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	// N = 300000;
	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 = rng() % OFFSET, cir[i].y = rng() % OFFSET, cir[i].r = exp(1.0 * rng() / mt19937::max() * log(10000));
		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) {
		if (c != vec.end() && c->r > ((1 << i) >> 1)) {
			grid.clear();
			for (auto t : vec) if (!~ans[t.i]) {
				grid[hsh(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) {
					if (grid.find(hsh(tx, ty)) == grid.end()) continue;
					vector<int> &cur = grid[hsh(tx, ty)], tmp;
					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 << ' ';
	cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
}

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