Submission #902378

#	Time	Username	Problem	Language	Result	Execution time	Memory
902378		Trisanu_Das	Circle selection (APIO18_circle_selection)	C++17	100 / 100	2595 ms	63380 KiB

circle_selection

#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
const int N = (int)3e5+ 7;
 
int x[N], y[N], r[N], n, ans[N], pos[N], block = 0;
map<pair<int, int>, vector<int>> mp;
set <int> ost;
 
ll sqr(ll x) {
	return x * x;
}
 
ll dist(int x1, int y1, int x2, int y2) {
	return sqr(x1 - x2) + sqr(y1 - y2);
}
 
void rescale() {
	mp.clear();
	for (int to : ost) mp[{x[to] / block, y[to] / block}].push_back(to);
}
 
main() {
	iota(pos, pos + N, 0);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d %d", &x[i], &y[i], &r[i]);
		ost.insert(i);
	}
	sort(pos + 1, pos + n + 1, [&](const int &A, const int &B) {
		if (r[A] == r[B]) return A < B;
		return r[A] > r[B];
	});
	for (int i = 1; i <= n; i++) {
		if (ans[pos[i]]) continue;
		if (block == 0 || r[pos[i]] * 2 <= block) {
			block = r[pos[i]];
			rescale();
		}
		for (int cx = x[pos[i]] / block - 2; cx <= x[pos[i]] / block + 2; cx++) {
			for (int cy = y[pos[i]] / block - 2; cy <= y[pos[i]] / block + 2; cy++) {
				if (!mp.count({cx, cy})) continue;
				for (int to : mp[{cx, cy}]) {
					if (!ans[to] && dist(x[pos[i]], y[pos[i]], x[to], y[to]) <= sqr(r[pos[i]] + r[to])) {
						ans[to] = pos[i];
						ost.erase(to);
					}
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
}

Compilation message (stderr)

circle_selection.cpp:24:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   24 | main() {
      | ^~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
circle_selection.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |   scanf("%d %d %d", &x[i], &y[i], &r[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