Submission #1217503

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217503		gs12117	Circle selection (APIO18_circle_selection)	C++20	100 / 100	1261 ms	536812 KiB

circle_selection

#include<cstdio>
#include<algorithm>
int n;
struct circ {
	long long int x, y, r, idx;
	bool operator<(const circ& rhs)const {
		if (r != rhs.r)return r > rhs.r;
		return idx < rhs.idx;
	}
};
circ c[300100];
circ sc[300100];
struct squ {
	long long int lx, rx, ly, ry;
};
int clist[7501000];
squ sqlist[7501000];
int sqln;
int cls[7501000];
int nclist[7501000];
squ nsqlist[7501000];
int nsqln;
int ncls[7501000];
long long int sqr;
int circsq[300100][25];
int circsql[300100];
int cchk[300100];
int ans[300100];
bool overlap(circ cir, squ sq) {
	bool xrange = false;
	bool yrange = false;
	if (cir.x >= sq.lx && cir.x <= sq.rx) {
		xrange = true;
	}
	if (cir.y >= sq.ly && cir.y <= sq.ry) {
		yrange = true;
	}
	if (xrange && yrange)return true;
	if (xrange) {
		if (cir.y + cir.r >= sq.ly && cir.y - cir.r <= sq.ry) {
			return true;
		}
		return false;
	}
	if (yrange) {
		if (cir.x + cir.r >= sq.lx && cir.x - cir.r <= sq.rx) {
			return true;
		}
		return false;
	}
	long long int lxdist = cir.x - sq.lx;
	long long int rxdist = cir.x - sq.rx;
	if (lxdist < 0)lxdist = -lxdist;
	if (rxdist < 0)rxdist = -rxdist;
	if (lxdist < rxdist)rxdist = lxdist;
	long long int lydist = cir.y - sq.ly;
	long long int rydist = cir.y - sq.ry;
	if (lydist < 0)lydist = -lydist;
	if (rydist < 0)rydist = -rydist;
	if (lydist < rydist)rydist = lydist;
	if (rxdist > cir.r || rydist > cir.r)return false;
	if (cir.r * cir.r >= rxdist * rxdist + rydist * rydist) {
		return true;
	}
	return false;
}
void inssq(squ sq, int s, int e) {
	nsqlist[nsqln] = sq;
	ncls[nsqln + 1] = ncls[nsqln];
	nsqln++;
	for (int i = s; i < e; i++) {
		int x = clist[i];
		if (cchk[x])continue;
		if (overlap(c[x], sq)) {
			nclist[ncls[nsqln]] = x;
			ncls[nsqln]++;
		}
	}
	if (ncls[nsqln] == ncls[nsqln - 1])nsqln--;
}
void cutsq() {
	sqr /= 2;
	nsqln = 0;
	ncls[0] = 0;
	for (int i = 0; i < sqln; i++) {
		squ csq = sqlist[i];
		long long int mx = (csq.lx + csq.rx) / 2;
		long long int my = (csq.ly + csq.ry) / 2;
		squ nsq;
		nsq.lx = csq.lx;
		nsq.rx = mx;
		nsq.ly = csq.ly;
		nsq.ry = my;
		inssq(nsq, cls[i], cls[i + 1]);
		nsq.lx = csq.lx;
		nsq.rx = mx;
		nsq.ly = my;
		nsq.ry = csq.ry;
		inssq(nsq, cls[i], cls[i + 1]);
		nsq.lx = mx;
		nsq.rx = csq.rx;
		nsq.ly = csq.ly;
		nsq.ry = my;
		inssq(nsq, cls[i], cls[i + 1]);
		nsq.lx = mx;
		nsq.rx = csq.rx;
		nsq.ly = my;
		nsq.ry = csq.ry;
		inssq(nsq, cls[i], cls[i + 1]);
	}
	sqln = nsqln;
	for (int i = 0; i < sqln; i++) {
		cls[i] = ncls[i];
		sqlist[i] = nsqlist[i];
	}
	cls[sqln] = ncls[sqln];
	for (int i = 0; i < cls[sqln]; i++) {
		clist[i] = nclist[i];
	}
	for (int i = 0; i < n; i++) {
		circsql[i] = 0;
	}
	for (int i = 0; i < sqln; i++) {
		for (int j = cls[i]; j < cls[i + 1]; j++) {
			circsq[clist[j]][circsql[clist[j]]] = i;
			circsql[clist[j]]++;
		}
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%lld%lld%lld", &c[i].x, &c[i].y, &c[i].r);
		c[i].idx = i;
		sc[i] = c[i];
	}
	std::sort(sc, sc + n);
	sqln = 1;
	sqlist[0].rx = (1LL << 32);
	sqlist[0].ry = sqlist[0].rx;
	sqlist[0].lx = -sqlist[0].rx;
	sqlist[0].ly = -sqlist[0].rx;
	for (int i = 0; i < n; i++) {
		clist[i] = i;
		circsq[i][0] = 0;
		circsql[i] = 1;
	}
	cls[0] = 0;
	cls[1] = n;
	sqr = sqlist[0].rx - sqlist[0].lx;
	for (int i = 0; i < n; i++) {
		int cidx = sc[i].idx;
		if (cchk[cidx] == 1)continue;
		long long int circr = sc[i].r;
		while (circr < sqr) {
			cutsq();
		}
		cchk[cidx] = 1;
		ans[cidx] = cidx;
		for (int j = 0; j < circsql[cidx]; j++) {
			int sqidx = circsq[cidx][j];
			for (int k = cls[sqidx]; k < cls[sqidx + 1]; k++) {
				int x = clist[k];
				if (cchk[x] == 1)continue;
				if ((c[x].r + c[cidx].r) * (c[x].r + c[cidx].r) >=
					(c[x].x - c[cidx].x) * (c[x].x - c[cidx].x) +
					(c[x].y - c[cidx].y) * (c[x].y - c[cidx].y)) {
					cchk[x] = 1;
					ans[x] = cidx;
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		printf("%d ", ans[i] + 1);
	}
	printf("\n");
	return 0;
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:131:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
circle_selection.cpp:133:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |                 scanf("%lld%lld%lld", &c[i].x, &c[i].y, &c[i].r);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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