제출 #1261708

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1261708		4QT0R	Circle selection (APIO18_circle_selection)	C++20	49 / 100	3136 ms	855556 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;
#define ll long long

struct my_hash{
	size_t operator()(const pair<ll,ll>& p) const {
		size_t h1 = hash<ll>()(p.first);
		size_t h2 = hash<ll>()(p.second);
        return h1 ^ (h2 + (h1<<7) + (h2>>2));
    }
};

ll n;
vector<array<ll, 3>> info;
unordered_map<pair<ll, ll>, unordered_set<ll>, my_hash> mp;
vector<ll> ans;
vector<bool> del;

ll grid_length;

ll sq(ll x)
{
	return x * x;
}

bool query(ll i, ll j)
{
	return (sq(info[i][0] - info[j][0]) + sq(info[i][1] - info[j][1])) <= sq(info[i][2] + info[j][2]);
}

void remake()
{
	mp.clear();
	for (ll i = 0; i < n; i++)
	{
		if (del[i])
			continue;
		mp[{info[i][0] / grid_length, info[i][1] / grid_length}].insert(i);
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	ans.resize(n);
	del.resize(n);
	for (ll i = 1, x, y, r; i <= n; i++)
	{
		cin >> x >> y >> r;
		info.push_back({x, y, r});
	}
	vector<ll> kol(n);
	iota(kol.begin(), kol.end(), 0);
	sort(kol.begin(), kol.end(), [&](ll a, ll b)
		 { return info[a][2] == info[b][2] ? a < b : info[a][2] > info[b][2]; });
	grid_length = info[kol[0]][2];
	remake();
	for (auto now : kol)
	{
		if (del[now])
			continue;
		if (2 * info[now][2] <= grid_length)
		{
			grid_length = info[now][2];
			remake();
		}
		ll cur_x = info[now][0] / grid_length;
		ll cur_y = info[now][1] / grid_length;
		vector<ll> deleted_now;
		for (ll x = -2; x <= 2; x++)
		{
			for (ll y = -2; y <= 2; y++)
			{
				for (auto ind : mp[{cur_x + x, cur_y + y}])
				{
					if (query(now, ind))
						deleted_now.push_back(ind);
				}
			}
		}
		while (deleted_now.size())
		{
			ll ind = deleted_now.back();
			deleted_now.pop_back();
			del[ind] = true;
			mp[{info[ind][0] / grid_length, info[ind][1] / grid_length}].erase(ind);
			ans[ind] = now;
		}
	}
	for (auto x : ans)
		cout << x+1 << ' ';
	cout << '\n';
}

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