Submission #381772

#	Time	Username	Problem	Language	Result	Execution time	Memory
381772		rainboy	Circle selection (APIO18_circle_selection)	C11	100 / 100	1068 ms	13036 KiB

circle_selection

/* https://oj.uz/submission/66132 (Benq) */
#include <stdio.h>
#include <string.h>

#define N	300000
#define X	1000000000

unsigned int Z = 12345;

int rand_() {
	return (Z *= 3) >> 1;
}

int xx[N], yy[N], rr[N];

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k) {
			int c = rr[ii[j]] != rr[i_] ? rr[i_] - rr[ii[j]] : ii[j] - i_;

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		}
		sort(ii, l, i);
		l = k;
	}
}

int ii_[N], xx_[N], yy_[N], n, lg;

int idx(int x, int y) {
	int lower = -1, upper = n;

	while (upper - lower > 1) {
		int i = (lower + upper) / 2, x_ = xx_[ii_[i]], y_ = yy_[ii_[i]];

		if (x_ < x || x_ == x && y_ <= y)
			lower = i;
		else
			upper = i;
	}
	return lower;
}

int main() {
	static int ii[N], ii1[N], pp[N];
	int h, h_, i, j, cnt;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d%d%d", &xx[i], &yy[i], &rr[i]);
		xx[i] += X, yy[i] += X;
		ii[i] = ii_[i] = i;
	}
	sort(ii, 0, n);
	memset(pp, -1, n * sizeof *pp);
	for (lg = 30, h = 0; lg >= 0; lg--) {
		int x, y, dx;

		for (i = 0; i < n; i++)
			xx_[i] = xx[i] >> lg + 1, yy_[i] = yy[i] >> lg + 1;
		while (h < n && rr[ii[h]] >= 1 << lg) {
			i = ii[h], x = xx_[i], y = yy_[i];
			if (pp[i] == -1)
				for (dx = -2; dx <= 2; dx++) {
					h_ = idx(x + dx, y - 3) + 1;
					while (h_ < n && xx_[ii_[h_]] == x + dx && yy_[ii_[h_]] <= y + 2) {
						j = ii_[h_];
						if (pp[j] == -1 && (long long) (xx[i] - xx[j]) * (xx[i] - xx[j]) + (long long) (yy[i] - yy[j]) * (yy[i] - yy[j]) <= (long long) (rr[i] + rr[j]) * (rr[i] + rr[j]))
							pp[j] = i;
						h_++;
					}
				}
			h++;
		}
		for (i = 0; i < n; i = j) {
			x = xx_[ii_[i]];
			j = i + 1;
			while (j < n && xx_[ii_[j]] == x)
				j++;
			cnt = 0;
			for (h_ = i; h_ < j; h_++)
				if ((xx[ii_[h_]] >> lg & 1) == 0)
					ii_[i++] = ii_[h_];
				else
					ii1[cnt++] = ii_[h_];
			memcpy(ii_ + i, ii1, cnt * sizeof *ii1);
		}
		for (i = 0; i < n; i = j) {
			x = xx[ii_[i]] >> lg, y = yy_[ii_[i]];
			j = i + 1;
			while (j < n && (xx[ii_[j]] >> lg) == x && yy_[ii_[j]] == y)
				j++;
			cnt = 0;
			for (h_ = i; h_ < j; h_++)
				if ((yy[ii_[h_]] >> lg & 1) == 0)
					ii_[i++] = ii_[h_];
				else
					ii1[cnt++] = ii_[h_];
			memcpy(ii_ + i, ii1, cnt * sizeof *ii1);
		}
	}
	for (i = 0; i < n; i++)
		printf("%d ", pp[i] + 1);
	printf("\n");
	return 0;
}

Compilation message (stderr)

circle_selection.c: In function 'idx':
circle_selection.c:46:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   46 |   if (x_ < x || x_ == x && y_ <= y)
      |                 ~~~~~~~~^~~~~~~~~~
circle_selection.c: In function 'main':
circle_selection.c:70:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |    xx_[i] = xx[i] >> lg + 1, yy_[i] = yy[i] >> lg + 1;
      |                      ~~~^~~
circle_selection.c:70:51: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |    xx_[i] = xx[i] >> lg + 1, yy_[i] = yy[i] >> lg + 1;
      |                                                ~~~^~~
circle_selection.c:58:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   58 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
circle_selection.c:60:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   60 |   scanf("%d%d%d", &xx[i], &yy[i], &rr[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