답안 #611075

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
611075	2022-07-29T02:10:20 Z	GusterGoose27	원 고르기 (APIO18_circle_selection)	C++11	100 / 100	2734 ms	59884 KB

circle_selection

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

class Circle {
public:
	int x;
	int y;
	int r;
	int id;
	bool active = 1;
	Circle() {}
	Circle(int xn, int yn, int rn, int i) {
		x = xn;
		y = yn;
		r = rn;
		id = i;
	}
};

bool operator<(Circle &a, Circle &b) {
	return (a.r == b.r) ? (a.id < b.id) : (a.r > b.r);
}

bool intersect(Circle &a, Circle &b) {
	ll xdiff = a.x-b.x;
	ll ydiff = a.y-b.y;
	ll rsum = a.r+b.r;
	return rsum*rsum >= xdiff*xdiff+ydiff*ydiff;
}

const int MAXN = 3e5;
int n;
Circle circles[MAXN];
map<pii, set<int>> grid_div;
int par[MAXN];
int sq_sz;

void make_div() {
	grid_div.clear();
	for (int i = 0; i < n; i++) {
		if (!circles[i].active) continue;
		grid_div[pii(circles[i].x/sq_sz, circles[i].y/sq_sz)].insert(i);
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x, y, r;
		cin >> x >> y >> r;
		circles[i] = Circle(x, y, r, i);
	}
	sort(circles, circles+n);
	sq_sz = circles[0].r;
	make_div();
	for (int i = 0; i < n; i++) {
		if (!circles[i].active) continue;
		if (circles[i].r <= sq_sz/2) {
			sq_sz = circles[i].r;
			make_div();
		}
		int sqx = circles[i].x/sq_sz;
		int sqy = circles[i].y/sq_sz;
		for (int x_diff = -2; x_diff <= 2; x_diff++) {
			for (int y_diff = -2; y_diff <= 2; y_diff++) {
				pii cur = pii(sqx+x_diff, sqy+y_diff);
				if (grid_div.find(cur) != grid_div.end()) {
					vector<int> r;
					for (int circ: grid_div[cur]) {
						if (intersect(circles[circ], circles[i])) {
							par[circles[circ].id] = circles[i].id;
							r.push_back(circ);
							circles[circ].active = 0;
						}
					}
					for (int circ: r) grid_div[cur].erase(circ);
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		if (i) cout << ' ';
		cout << (1+par[i]);
	}
	cout << "\n";
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	6100 KB	Output is correct
2	Correct	3 ms	6100 KB	Output is correct
3	Correct	3 ms	6100 KB	Output is correct
4	Correct	3 ms	6100 KB	Output is correct
5	Correct	2 ms	6204 KB	Output is correct
6	Correct	3 ms	6204 KB	Output is correct
7	Correct	3 ms	6100 KB	Output is correct
8	Correct	3 ms	6100 KB	Output is correct
9	Correct	4 ms	6100 KB	Output is correct
10	Correct	3 ms	6100 KB	Output is correct
11	Correct	3 ms	6200 KB	Output is correct
12	Correct	3 ms	6100 KB	Output is correct
13	Correct	3 ms	6228 KB	Output is correct
14	Correct	3 ms	6100 KB	Output is correct
15	Correct	3 ms	6100 KB	Output is correct
16	Correct	3 ms	6228 KB	Output is correct
17	Correct	3 ms	6228 KB	Output is correct
18	Correct	3 ms	6228 KB	Output is correct
19	Correct	6 ms	6604 KB	Output is correct
20	Correct	6 ms	6612 KB	Output is correct
21	Correct	6 ms	6580 KB	Output is correct
22	Correct	15 ms	6984 KB	Output is correct
23	Correct	16 ms	6996 KB	Output is correct
24	Correct	16 ms	6996 KB	Output is correct
25	Correct	13 ms	7056 KB	Output is correct
26	Correct	14 ms	6996 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	227 ms	30368 KB	Output is correct
2	Correct	288 ms	30308 KB	Output is correct
3	Correct	208 ms	30108 KB	Output is correct
4	Correct	186 ms	30348 KB	Output is correct
5	Correct	418 ms	28528 KB	Output is correct
6	Correct	768 ms	41868 KB	Output is correct
7	Correct	395 ms	29720 KB	Output is correct
8	Correct	541 ms	32052 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	6100 KB	Output is correct
2	Correct	510 ms	23948 KB	Output is correct
3	Correct	1881 ms	59656 KB	Output is correct
4	Correct	1801 ms	59652 KB	Output is correct
5	Correct	1813 ms	53916 KB	Output is correct
6	Correct	625 ms	30168 KB	Output is correct
7	Correct	248 ms	19020 KB	Output is correct
8	Correct	39 ms	8868 KB	Output is correct
9	Correct	2062 ms	58900 KB	Output is correct
10	Correct	1570 ms	52936 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1508 ms	59516 KB	Output is correct
2	Correct	1116 ms	58680 KB	Output is correct
3	Correct	576 ms	39524 KB	Output is correct
4	Correct	1093 ms	59116 KB	Output is correct
5	Correct	1111 ms	59336 KB	Output is correct
6	Correct	441 ms	32900 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	6100 KB	Output is correct
2	Correct	3 ms	6100 KB	Output is correct
3	Correct	3 ms	6100 KB	Output is correct
4	Correct	3 ms	6100 KB	Output is correct
5	Correct	2 ms	6204 KB	Output is correct
6	Correct	3 ms	6204 KB	Output is correct
7	Correct	3 ms	6100 KB	Output is correct
8	Correct	3 ms	6100 KB	Output is correct
9	Correct	4 ms	6100 KB	Output is correct
10	Correct	3 ms	6100 KB	Output is correct
11	Correct	3 ms	6200 KB	Output is correct
12	Correct	3 ms	6100 KB	Output is correct
13	Correct	3 ms	6228 KB	Output is correct
14	Correct	3 ms	6100 KB	Output is correct
15	Correct	3 ms	6100 KB	Output is correct
16	Correct	3 ms	6228 KB	Output is correct
17	Correct	3 ms	6228 KB	Output is correct
18	Correct	3 ms	6228 KB	Output is correct
19	Correct	6 ms	6604 KB	Output is correct
20	Correct	6 ms	6612 KB	Output is correct
21	Correct	6 ms	6580 KB	Output is correct
22	Correct	15 ms	6984 KB	Output is correct
23	Correct	16 ms	6996 KB	Output is correct
24	Correct	16 ms	6996 KB	Output is correct
25	Correct	13 ms	7056 KB	Output is correct
26	Correct	14 ms	6996 KB	Output is correct
27	Correct	9 ms	6996 KB	Output is correct
28	Correct	9 ms	7116 KB	Output is correct
29	Correct	8 ms	7012 KB	Output is correct
30	Correct	33 ms	7892 KB	Output is correct
31	Correct	28 ms	7876 KB	Output is correct
32	Correct	28 ms	7872 KB	Output is correct
33	Correct	68 ms	15036 KB	Output is correct
34	Correct	71 ms	15372 KB	Output is correct
35	Correct	102 ms	14964 KB	Output is correct
36	Correct	402 ms	23708 KB	Output is correct
37	Correct	439 ms	23836 KB	Output is correct
38	Correct	425 ms	23884 KB	Output is correct
39	Correct	680 ms	20900 KB	Output is correct
40	Correct	627 ms	20984 KB	Output is correct
41	Correct	651 ms	20896 KB	Output is correct
42	Correct	284 ms	22784 KB	Output is correct
43	Correct	298 ms	23656 KB	Output is correct
44	Correct	283 ms	23596 KB	Output is correct
45	Correct	284 ms	23648 KB	Output is correct
46	Correct	315 ms	23552 KB	Output is correct
47	Correct	297 ms	23628 KB	Output is correct
48	Correct	307 ms	23568 KB	Output is correct
49	Correct	282 ms	23572 KB	Output is correct
50	Correct	329 ms	23576 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	6100 KB	Output is correct
2	Correct	3 ms	6100 KB	Output is correct
3	Correct	3 ms	6100 KB	Output is correct
4	Correct	3 ms	6100 KB	Output is correct
5	Correct	2 ms	6204 KB	Output is correct
6	Correct	3 ms	6204 KB	Output is correct
7	Correct	3 ms	6100 KB	Output is correct
8	Correct	3 ms	6100 KB	Output is correct
9	Correct	4 ms	6100 KB	Output is correct
10	Correct	3 ms	6100 KB	Output is correct
11	Correct	3 ms	6200 KB	Output is correct
12	Correct	3 ms	6100 KB	Output is correct
13	Correct	3 ms	6228 KB	Output is correct
14	Correct	3 ms	6100 KB	Output is correct
15	Correct	3 ms	6100 KB	Output is correct
16	Correct	3 ms	6228 KB	Output is correct
17	Correct	3 ms	6228 KB	Output is correct
18	Correct	3 ms	6228 KB	Output is correct
19	Correct	6 ms	6604 KB	Output is correct
20	Correct	6 ms	6612 KB	Output is correct
21	Correct	6 ms	6580 KB	Output is correct
22	Correct	15 ms	6984 KB	Output is correct
23	Correct	16 ms	6996 KB	Output is correct
24	Correct	16 ms	6996 KB	Output is correct
25	Correct	13 ms	7056 KB	Output is correct
26	Correct	14 ms	6996 KB	Output is correct
27	Correct	227 ms	30368 KB	Output is correct
28	Correct	288 ms	30308 KB	Output is correct
29	Correct	208 ms	30108 KB	Output is correct
30	Correct	186 ms	30348 KB	Output is correct
31	Correct	418 ms	28528 KB	Output is correct
32	Correct	768 ms	41868 KB	Output is correct
33	Correct	395 ms	29720 KB	Output is correct
34	Correct	541 ms	32052 KB	Output is correct
35	Correct	3 ms	6100 KB	Output is correct
36	Correct	510 ms	23948 KB	Output is correct
37	Correct	1881 ms	59656 KB	Output is correct
38	Correct	1801 ms	59652 KB	Output is correct
39	Correct	1813 ms	53916 KB	Output is correct
40	Correct	625 ms	30168 KB	Output is correct
41	Correct	248 ms	19020 KB	Output is correct
42	Correct	39 ms	8868 KB	Output is correct
43	Correct	2062 ms	58900 KB	Output is correct
44	Correct	1570 ms	52936 KB	Output is correct
45	Correct	1508 ms	59516 KB	Output is correct
46	Correct	1116 ms	58680 KB	Output is correct
47	Correct	576 ms	39524 KB	Output is correct
48	Correct	1093 ms	59116 KB	Output is correct
49	Correct	1111 ms	59336 KB	Output is correct
50	Correct	441 ms	32900 KB	Output is correct
51	Correct	9 ms	6996 KB	Output is correct
52	Correct	9 ms	7116 KB	Output is correct
53	Correct	8 ms	7012 KB	Output is correct
54	Correct	33 ms	7892 KB	Output is correct
55	Correct	28 ms	7876 KB	Output is correct
56	Correct	28 ms	7872 KB	Output is correct
57	Correct	68 ms	15036 KB	Output is correct
58	Correct	71 ms	15372 KB	Output is correct
59	Correct	102 ms	14964 KB	Output is correct
60	Correct	402 ms	23708 KB	Output is correct
61	Correct	439 ms	23836 KB	Output is correct
62	Correct	425 ms	23884 KB	Output is correct
63	Correct	680 ms	20900 KB	Output is correct
64	Correct	627 ms	20984 KB	Output is correct
65	Correct	651 ms	20896 KB	Output is correct
66	Correct	284 ms	22784 KB	Output is correct
67	Correct	298 ms	23656 KB	Output is correct
68	Correct	283 ms	23596 KB	Output is correct
69	Correct	284 ms	23648 KB	Output is correct
70	Correct	315 ms	23552 KB	Output is correct
71	Correct	297 ms	23628 KB	Output is correct
72	Correct	307 ms	23568 KB	Output is correct
73	Correct	282 ms	23572 KB	Output is correct
74	Correct	329 ms	23576 KB	Output is correct
75	Correct	246 ms	32940 KB	Output is correct
76	Correct	277 ms	32368 KB	Output is correct
77	Correct	208 ms	32588 KB	Output is correct
78	Correct	250 ms	32604 KB	Output is correct
79	Correct	369 ms	32268 KB	Output is correct
80	Correct	239 ms	32576 KB	Output is correct
81	Correct	1858 ms	59680 KB	Output is correct
82	Correct	1799 ms	59416 KB	Output is correct
83	Correct	1804 ms	59372 KB	Output is correct
84	Correct	2118 ms	59884 KB	Output is correct
85	Correct	1884 ms	59448 KB	Output is correct
86	Correct	1990 ms	59532 KB	Output is correct
87	Correct	2382 ms	59432 KB	Output is correct
88	Correct	2616 ms	50716 KB	Output is correct
89	Correct	2686 ms	50688 KB	Output is correct
90	Correct	2734 ms	50860 KB	Output is correct
91	Correct	2428 ms	50848 KB	Output is correct
92	Correct	2421 ms	50628 KB	Output is correct
93	Correct	1379 ms	58452 KB	Output is correct
94	Correct	1497 ms	58688 KB	Output is correct
95	Correct	1353 ms	58572 KB	Output is correct
96	Correct	1405 ms	58464 KB	Output is correct
97	Correct	2225 ms	58384 KB	Output is correct
98	Correct	943 ms	48532 KB	Output is correct
99	Correct	1394 ms	58628 KB	Output is correct
100	Correct	1297 ms	58428 KB	Output is correct
101	Correct	1203 ms	52832 KB	Output is correct
102	Correct	1311 ms	58116 KB	Output is correct
103	Correct	1915 ms	58136 KB	Output is correct
104	Correct	1384 ms	58308 KB	Output is correct
105	Correct	1117 ms	56128 KB	Output is correct
106	Correct	1024 ms	57440 KB	Output is correct
107	Correct	1026 ms	57520 KB	Output is correct
108	Correct	1018 ms	57468 KB	Output is correct
109	Correct	1028 ms	57468 KB	Output is correct
110	Correct	1050 ms	57556 KB	Output is correct
111	Correct	1071 ms	57588 KB	Output is correct
112	Correct	1063 ms	57500 KB	Output is correct
113	Correct	1092 ms	57520 KB	Output is correct
114	Correct	1090 ms	57424 KB	Output is correct
115	Correct	1104 ms	57512 KB	Output is correct
116	Correct	1071 ms	57468 KB	Output is correct

답안 #611075

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 12.0 / 12.0

Subtask #3 15.0 / 15.0

Subtask #4 23.0 / 23.0

Subtask #5 30.0 / 30.0

Subtask #6 13.0 / 13.0

Subtask #1
7.0 / 7.0

Subtask #2
12.0 / 12.0

Subtask #3
15.0 / 15.0

Subtask #4
23.0 / 23.0

Subtask #5
30.0 / 30.0

Subtask #6
13.0 / 13.0