Submission #111248

#	Time	Username	Problem	Language	Result	Execution time	Memory
111248		Just_Solve_The_Problem	Circle selection (APIO18_circle_selection)	C++17	72 / 100	3031 ms	55376 KiB

circle_selection

#include <set>
#include <map>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <numeric>
#pragma GCC optimize("Ofast")
 
#define ll long long
 
using namespace std;
 
const int N = (int)3e5 + 7;
 
int x[N], y[N], r[N];
int n;
int ans[N];
map<pair<int, int>, vector<int>> mp;
int pos[N];
int block = 0;
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]);
	}
}
/*
11
9 9 3
13 2 3
11 8 3
3 3 3
3 12 3
12 14 3
9 8 3
2 8 3
5 2 3
14 4 3
14 14 3
*/

Compilation message (stderr)

circle_selection.cpp:38:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
circle_selection.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &x[i], &y[i], &r[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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