Submission #373399

#	Time	Username	Problem	Language	Result	Execution time	Memory
373399		LucaDantas	Circle selection (APIO18_circle_selection)	C++17	0 / 100	45 ms	4716 KiB

circle_selection

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

#define pb push_back

constexpr int maxn = 1e5+10;

struct Circle
{
	int x, y, r, id;
	void db() {
		printf("(%d %d %d) ", x, y, r);
	}
} cc[maxn];

long long sq(int x) { return 1ll * x * x; }
bool intersect(Circle a, Circle b) {
	return sq(a.x - b.x) + sq(a.y - b.y) <= sq(a.r + b.r);
}

int B, n, ans[maxn];

vector<vector<Circle>> blocks;

void setBlocks() {
	sort(cc, cc+n, [](Circle a, Circle b) {
		if((a.x>>B) != (b.x>>B)) return a.x < b.x;
		return a.y < b.y;
	});
	vector<Circle> here = {cc[0]};
	for(int i = 1, last = cc[0].x; i < n; i++) {
		if((last>>B) == (cc[i].x>>B)) here.pb(cc[i]);
		else blocks.pb(here), here = {cc[i]};
		last = cc[i].x;
	}
	blocks.pb(here);
}

void doit(int i, int c) {
	int L = 0, R = (int)blocks[i].size()-1, best = -1, index = (cc[c].y>>B);
	while(L <= R) {
		int m = (L+R) >> 1;
		// printf("L, R, m %d %d %d\n", L, R, m);
		if((blocks[i][m].y>>B) >= index-2) best = m, R = m-1;
		else L = m+1;
	}
	// puts("SAIU");
	if(best == -1) return;
	// puts("ORIGEM");
	// cc[c].db(); puts("\nOLHA");
	for(; best < (int)blocks[i].size() && (blocks[i][best].y>>B) <= index+2; ++best) {
		// blocks[i][best].db();
		if(intersect(cc[c], blocks[i][best]) && !ans[blocks[i][best].id])
			ans[blocks[i][best].id] = cc[c].id+1;
	}
	// puts("");
}

int main() {
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
		scanf("%d %d %d", &cc[i].x, &cc[i].y, &cc[i].r);
		cc[i].id = i; B = max(B, cc[i].r);
	}
	// imagine I don't need to rescale
	// B = 32 - __builtin_clz(B-1);
	setBlocks();

	// for(auto x : blocks) {
	// 	for(Circle y : x)
	// 		y.db();
	// 	printf("\n");
	// }
	sort(cc, cc+n, [](Circle a, Circle b) {
		if(a.r == b.r) return a.id < b.id;
		return a.r > b.r;
	});
	for(int i = 0; i < n; i++) {
		if(ans[cc[i].id]) continue;
		// ans[cc[i].id] = cc[i].id+1;
		auto [x, y, r, id] = cc[i];
		// imagine we don't need to rescale
		// while((1 << B) >= (r << 1))
		// 	--B, rescale();

		int L = 0, R = (int)blocks.size()-1, best = -1, index = (r>>B);
		// first with index greater than or equal to mine-2
		while(L <= R) {
			int m = (L+R) >> 1;
			if((blocks[m][0].x>>B) >= index-2) best = m, R = m-1;
			else L = m+1;
		}
		if(best == -1) continue;
		while(best < (int)blocks.size() && (blocks[best][0].x>>B) <= index+2)
			doit(best, i), ++best;
		// puts("");
	}

	sort(cc, cc+n, [](Circle a, Circle b) { return a.id < b.id; });
	for(int i = 0; i < n; i++)
		printf("%d ", ans[i]);
	puts("");
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
circle_selection.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |   scanf("%d %d %d", &cc[i].x, &cc[i].y, &cc[i].r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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