oj.uz

답안 #381739

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
381739 2021-03-25T19:55:45 Z rainboy 새 집 (APIO18_new_home) C
0 / 100
 3396 ms 72792 KB 
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <stdio.h>
#include <string.h>

#define N	300000
#define X	1000000000
#define C	25

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 compare(int x1, int y1, int x2, int y2) {
	return x1 != x2 ? x1 - x2 : y1 - y2;
}

int main() {
	static char type[N];
	static int xx_[N], yy_[N], ii[N], ii_[N], tmp[N], ggg[N][C], gg[C], iii[N][C * 4], kk[N], pp[N];
	int n, g, h, h_, i, j, k, c, lg, 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--) {
		int x, y;

		for (i = 0; i < n; i++)
			xx_[i] = xx[i] >> lg + 1, yy_[i] = yy[i] >> lg + 1;
		memset(gg, 0, C * sizeof *gg);
		for (h_ = 0; h_ < n; h_++) {
			i = ii_[h_], x = xx_[i], y = yy_[i];
			for (c = 0; c < C; c++) {
				int dx = c / 5 - 2, dy = c % 5 - 2;

				while (gg[c] < n && compare(xx_[ii_[gg[c]]], yy_[ii_[gg[c]]], x + dx, y + dy) < 0)
					gg[c]++;
				ggg[i][c] = gg[c] < n && compare(xx_[ii_[gg[c]]], yy_[ii_[gg[c]]], x + dx, y + dy) == 0 ? gg[c] : -1;
			}
		}
		memset(kk, 0, n * sizeof *kk);
		for (h_ = h; h_ < n; h_++) {
			int p;

			i = ii[h_], x = xx_[i], y = yy_[i], p = -1;
			if (type[i] == -1)
				continue;
			g = ggg[i][(0 + 2) * 5 + (0 + 2)];
			if (g != -1)
				for (k = 0; k < kk[g]; k++) {
					j = iii[g][k];
					if (intersect(i, j)) {
						if (p == -1 || rr[p] < rr[j] || rr[p] == rr[j] && p > j)
							p = j;
						break;
					}
				}
			if (p != -1)
				pp[i] = p, type[i] = -1;
			else {
				pp[i] = i, type[i] = 1;
				if (rr[i] >= 1 << lg)
					for (c = 0; c < C; c++) {
						g = ggg[i][c];
						if (g != -1)
							iii[g][kk[g]++] = i;
					}
			}
		}
		while (h < n && rr[ii[h]] >= 1 << lg)
			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
					tmp[cnt++] = ii_[h_];
			memcpy(ii_ + i, tmp, cnt * sizeof *tmp);
		}
		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
					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

new_home.c: In function 'main':
new_home.c:67:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |    xx_[i] = xx[i] >> lg + 1, yy_[i] = yy[i] >> lg + 1;
      |                      ~~~^~~
new_home.c:67:51: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |    xx_[i] = xx[i] >> lg + 1, yy_[i] = yy[i] >> lg + 1;
      |                                                ~~~^~~
new_home.c:91:54: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   91 |       if (p == -1 || rr[p] < rr[j] || rr[p] == rr[j] && p > j)
      |                                       ~~~~~~~~~~~~~~~^~~~~~~~
new_home.c:56:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   56 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
new_home.c:58:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   58 |   scanf("%d%d%d", &xx[i], &yy[i], &rr[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2887 ms 52256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3396 ms 72792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -