제출 #1209093

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1209093		k1r1t0	원 고르기 (APIO18_circle_selection)	C++20	100 / 100	2384 ms	198264 KiB

circle_selection

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using ld = long double;
 
struct pt {int x, y; pt() {} pt(int _x, int _y) : x(_x), y(_y) {}};
pt operator -(pt a, pt b) {return {a.x - b.x, a.y - b.y};}
pt operator +(pt a, pt b) {return {a.x + b.x, a.y + b.y};}
ll lensqr(pt a) {return 1ll * a.x * a.x + 1ll * a.y * a.y;}
 
const int K = 31;
const int N = 310000;
const int INF = (int)(1e9);
const ld BASE = 10;
const int MP_COUNT = 100;
 
int n, m, r[N], ans[N];
vector<int> tt;
pt p[N];
unordered_map<ll, vector<int>> mp[MP_COUNT];
 
bool good(int i, int j) {
	return lensqr(p[i] - p[j]) <= 1ll * (r[i] + r[j]) * (r[i] + r[j]);
}
 
int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	ld cur = 1;
	tt.push_back(cur);
	while (cur < INF) {
		cur *= BASE;
		tt.push_back(cur);
	}
	tt.erase(unique(begin(tt), end(tt)), end(tt));
	m = (int) tt.size();
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> p[i].x >> p[i].y >> r[i];
		p[i] = p[i] + pt(INF, INF);
		for (int j = 0; j < m; j++)
			mp[j][(((ll) p[i].x / tt[j]) << K) + (p[i].y / tt[j])].push_back(i);
	}
	vector<int> ord(n);
	iota(begin(ord), end(ord), 1);
	sort(begin(ord), end(ord), [&](int i, int j) {
		return r[i] > r[j] || (r[i] == r[j] && i < j);
	});
	for (int k : ord) {
		if (ans[k]) continue;
		int t = 0;
		while (tt[t] < r[k])
			t++;
		int bx = p[k].x / tt[t];
		int by = p[k].y / tt[t];
		for (int dx = -2; dx <= 2; dx++)
		for (int dy = -2; dy <= 2; dy++) {
			int cx = bx + dx;
			int cy = by + dy;
			ll id = (((ll) cx) << K) + cy;
			if (mp[t].find(id) == mp[t].end())
				continue;
			if (mp[t][id].empty()) {
				mp[t].erase(id);
				continue;
			}
			vector<int> vec;
			for (auto i : mp[t][id]) {
				if (ans[i]) continue;
				if (good(i, k)) ans[i] = k;
				else vec.push_back(i);
			}
			mp[t][id] = vec;
		}
	}
	for (int i = 1; i <= n; i++)
		cout << ans[i] << ' ';
}

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