Submission #381274

#	Time	Username	Problem	Language	Result	Execution time	Memory
381274		rainboy	Circle selection (APIO18_circle_selection)	C11	0 / 100	1366 ms	16656 KiB

circle_selection

#include <assert.h>
#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];

int intersect(int i, int j) {
	long long x = xx[i] - xx[j], y = yy[i] - yy[j], r = rr[i] + rr[j];

	return x * x + y * y <= r * r;
}

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], 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]] >> lg + 1, y_ = yy[ii_[i]] >> lg + 1;

		if (x_ < x || x_ == x && y_ <= y)
			lower = i;
		else
			upper = i;
	}
	return lower != -1 && xx[ii_[lower]] >> lg + 1 == x && yy[ii_[lower]] >> lg + 1 == y ? lower : -1;
}

int main() {
	static char root[N];
	static int iii[N][4], kk[N], ii[N], tmp[N], pp[N];
	int g, 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);
	for (lg = 30, h = 0; lg >= 0; lg--) {
		memset(kk, 0, n * sizeof *kk);
		for (i = n - 1, j = n - 1; i >= 0; i--) {
			if (xx[ii_[i]] >> lg + 1 != xx[ii_[j]] >> lg + 1 || yy[ii_[i]] >> lg + 1 != yy[ii_[j]] >> lg + 1)
				j = i;
			if (root[ii_[i]])
				assert(kk[j] != 4), iii[j][kk[j]++] = ii_[i];
		}
		while (h < n && rr[ii[h]] >= 1 << lg) {
			int i_ = ii[h], x = xx[i_] >> lg + 1, y = yy[i_] >> lg + 1, dx, dy, p;

			p = -1;
			for (dx = -1; dx <= 1; dx++)
				for (dy = -1; dy <= 1; dy++) {
					g = idx(x + dx, y + dy);
					for (h_ = 0; h_ < kk[g]; h_++) {
						int j_ = iii[g][h_];

						if (intersect(i_, j_) && (p == -1 || rr[p] < rr[j_] || rr[p] == rr[j_] && p > j_))
							p = j_;
					}
				}
			if (p != -1)
				pp[i_] = p;
			else {
				pp[i_] = i_, root[i_] = 1;
				g = idx(x, y);
				assert(kk[g] != 4);
				iii[g][kk[g]++] = i_;
			}
			h++;
		}
		for (i = 0; i < n; i = j) {
			int x = xx[ii_[i]] >> lg + 1;

			j = i + 1;
			while (j < n && (xx[ii_[j]] >> lg + 1) == x)
				j++;
			cnt = 0;
			for (h_ = i; h_ < j; h_++)
				if ((xx[ii_[h_]] >> lg & 1) == 0)
					ii_[i++] = ii_[h_];
				else
					tmp[cnt++] = ii_[h_];
			memcpy(ii_ + i, tmp, cnt * sizeof *tmp);
		}
		for (i = 0; i < n; i = j) {
			int x = xx[ii_[i]] >> lg, y = yy[ii_[i]] >> lg + 1;

			j = i + 1;
			while (j < n && (xx[ii_[j]] >> lg) == x && (yy[ii_[j]] >> lg + 1) == y)
				j++;
			cnt = 0;
			for (h_ = i; h_ < j; h_++)
				if ((yy[ii_[h_]] >> lg & 1) == 0)
					ii_[i++] = ii_[h_];
				else
					tmp[cnt++] = ii_[h_];
			memcpy(ii_ + i, tmp, cnt * sizeof *tmp);
		}
	}
	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:50:54: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |   int i = (lower + upper) / 2, x_ = xx[ii_[i]] >> lg + 1, y_ = yy[ii_[i]] >> lg + 1;
      |                                                   ~~~^~~
circle_selection.c:50:81: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |   int i = (lower + upper) / 2, x_ = xx[ii_[i]] >> lg + 1, y_ = yy[ii_[i]] >> lg + 1;
      |                                                                              ~~~^~~
circle_selection.c:52:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   52 |   if (x_ < x || x_ == x && y_ <= y)
      |                 ~~~~~~~~^~~~~~~~~~
circle_selection.c:57:45: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |  return lower != -1 && xx[ii_[lower]] >> lg + 1 == x && yy[ii_[lower]] >> lg + 1 == y ? lower : -1;
      |                                          ~~~^~~
circle_selection.c:57:78: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |  return lower != -1 && xx[ii_[lower]] >> lg + 1 == x && yy[ii_[lower]] >> lg + 1 == y ? lower : -1;
      |                                                                           ~~~^~~
circle_selection.c: In function 'main':
circle_selection.c:75:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |    if (xx[ii_[i]] >> lg + 1 != xx[ii_[j]] >> lg + 1 || yy[ii_[i]] >> lg + 1 != yy[ii_[j]] >> lg + 1)
      |                      ~~~^~~
circle_selection.c:75:49: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |    if (xx[ii_[i]] >> lg + 1 != xx[ii_[j]] >> lg + 1 || yy[ii_[i]] >> lg + 1 != yy[ii_[j]] >> lg + 1)
      |                                              ~~~^~~
circle_selection.c:75:73: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |    if (xx[ii_[i]] >> lg + 1 != xx[ii_[j]] >> lg + 1 || yy[ii_[i]] >> lg + 1 != yy[ii_[j]] >> lg + 1)
      |                                                                      ~~~^~~
circle_selection.c:75:97: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |    if (xx[ii_[i]] >> lg + 1 != xx[ii_[j]] >> lg + 1 || yy[ii_[i]] >> lg + 1 != yy[ii_[j]] >> lg + 1)
      |                                                                                              ~~~^~~
circle_selection.c:81:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |    int i_ = ii[h], x = xx[i_] >> lg + 1, y = yy[i_] >> lg + 1, dx, dy, p;
      |                                  ~~~^~~
circle_selection.c:81:59: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |    int i_ = ii[h], x = xx[i_] >> lg + 1, y = yy[i_] >> lg + 1, dx, dy, p;
      |                                                        ~~~^~~
circle_selection.c:90:78: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   90 |       if (intersect(i_, j_) && (p == -1 || rr[p] < rr[j_] || rr[p] == rr[j_] && p > j_))
      |                                                              ~~~~~~~~~~~~~~~~^~~~~~~~~
circle_selection.c:105:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |    int x = xx[ii_[i]] >> lg + 1;
      |                          ~~~^~~
circle_selection.c:108:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |    while (j < n && (xx[ii_[j]] >> lg + 1) == x)
      |                                   ~~~^~~
circle_selection.c:119:51: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  119 |    int x = xx[ii_[i]] >> lg, y = yy[ii_[i]] >> lg + 1;
      |                                                ~~~^~~
circle_selection.c:122:65: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  122 |    while (j < n && (xx[ii_[j]] >> lg) == x && (yy[ii_[j]] >> lg + 1) == y)
      |                                                              ~~~^~~
circle_selection.c:65:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   65 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
circle_selection.c:67:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   67 |   scanf("%d%d%d", &xx[i], &yy[i], &rr[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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