답안 #251488

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
251488	2020-07-21T13:08:19 Z	oolimry	원 고르기 (APIO18_circle_selection)	C++14	100 / 100	1150 ms	49668 KB

circle_selection

#include <bits/stdc++.h>
 
using namespace std; 
int n; 
 
struct Circle{
	long long x, y, r, id;
} arr[300005];
 
bool intersect(Circle a, Circle b){
	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) <= (a.r + b.r) * (a.r + b.r);
}
 
long long ans[300005];
bool used[300005];

inline long long ii(long long a, long long b){
	return a * (1LL << 32LL) + b;
}
 
unordered_map<long long, vector<int> > GRID;
long long gridSize = 1LL << 31LL;
 
void buildGrid(long long newGridSize){
	gridSize = newGridSize;
	GRID.clear();
	
	for(int i = 0;i < n;i++){
		if(!used[i]){
			long long xSquare = arr[i].x / gridSize;
			long long ySquare = arr[i].y / gridSize;
			GRID[ii(xSquare,ySquare)].push_back(i);
		}
	}
}
 
bool comp(Circle a, Circle b){
	if(a.r == b.r) return a.id < b.id;
	else return a.r > b.r;
}
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n;
	fill(ans, ans + n, -1);
	
	for(int i = 0;i < n;i++){
		long long x, y, r; cin >> x >> y >> r;
		x += (1LL << 30LL); y += (1LL << 30LL);
		arr[i] = {x, y, r, i};
	}
	
	sort(arr,arr+n,comp);
	
	for(int i = 0;i < n;i++){
		Circle C = arr[i];
		
		if(used[i]) continue;
		
		if(gridSize > 2LL * C.r){
			buildGrid(C.r);
		}
		
		long long xSquare = C.x / gridSize;
		long long ySquare = C.y / gridSize;
		
		for(long long x = xSquare - 2;x <= xSquare + 2;x++){
			for(long long y = ySquare - 2;y <= ySquare + 2;y++){
				
				if(GRID.find(ii(x,y)) == GRID.end()) continue;
				vector<int> &points = GRID[ii(x,y)];
				
				for(int p = 0;p < (int) points.size();p++){
					if(intersect(arr[points[p]], C)){
						ans[arr[points[p]].id] = C.id;
						used[points[p]] = true;
												
						points[p] = points.back();
						points.pop_back();
						p--;
					}
				}
			}
		}
	}
	
	for(int i = 0;i < n;i++) cout << ans[i] + 1 << " ";
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	0 ms	384 KB	Output is correct
9	Correct	0 ms	384 KB	Output is correct
10	Correct	0 ms	384 KB	Output is correct
11	Correct	0 ms	384 KB	Output is correct
12	Correct	0 ms	384 KB	Output is correct
13	Correct	0 ms	384 KB	Output is correct
14	Correct	1 ms	384 KB	Output is correct
15	Correct	1 ms	384 KB	Output is correct
16	Correct	1 ms	384 KB	Output is correct
17	Correct	1 ms	384 KB	Output is correct
18	Correct	1 ms	384 KB	Output is correct
19	Correct	4 ms	768 KB	Output is correct
20	Correct	4 ms	768 KB	Output is correct
21	Correct	4 ms	768 KB	Output is correct
22	Correct	9 ms	1152 KB	Output is correct
23	Correct	9 ms	1152 KB	Output is correct
24	Correct	9 ms	1152 KB	Output is correct
25	Correct	9 ms	1152 KB	Output is correct
26	Correct	9 ms	1152 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	212 ms	21440 KB	Output is correct
2	Correct	211 ms	21436 KB	Output is correct
3	Correct	215 ms	22212 KB	Output is correct
4	Correct	211 ms	22064 KB	Output is correct
5	Correct	267 ms	19740 KB	Output is correct
6	Correct	487 ms	32312 KB	Output is correct
7	Correct	291 ms	21380 KB	Output is correct
8	Correct	341 ms	24516 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	260 ms	16380 KB	Output is correct
3	Correct	870 ms	49412 KB	Output is correct
4	Correct	823 ms	49544 KB	Output is correct
5	Correct	790 ms	44676 KB	Output is correct
6	Correct	296 ms	22712 KB	Output is correct
7	Correct	125 ms	12164 KB	Output is correct
8	Correct	22 ms	2944 KB	Output is correct
9	Correct	879 ms	48816 KB	Output is correct
10	Correct	796 ms	44216 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	961 ms	49284 KB	Output is correct
2	Correct	903 ms	48392 KB	Output is correct
3	Correct	332 ms	30600 KB	Output is correct
4	Correct	822 ms	48780 KB	Output is correct
5	Correct	864 ms	49028 KB	Output is correct
6	Correct	260 ms	25976 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	0 ms	384 KB	Output is correct
9	Correct	0 ms	384 KB	Output is correct
10	Correct	0 ms	384 KB	Output is correct
11	Correct	0 ms	384 KB	Output is correct
12	Correct	0 ms	384 KB	Output is correct
13	Correct	0 ms	384 KB	Output is correct
14	Correct	1 ms	384 KB	Output is correct
15	Correct	1 ms	384 KB	Output is correct
16	Correct	1 ms	384 KB	Output is correct
17	Correct	1 ms	384 KB	Output is correct
18	Correct	1 ms	384 KB	Output is correct
19	Correct	4 ms	768 KB	Output is correct
20	Correct	4 ms	768 KB	Output is correct
21	Correct	4 ms	768 KB	Output is correct
22	Correct	9 ms	1152 KB	Output is correct
23	Correct	9 ms	1152 KB	Output is correct
24	Correct	9 ms	1152 KB	Output is correct
25	Correct	9 ms	1152 KB	Output is correct
26	Correct	9 ms	1152 KB	Output is correct
27	Correct	7 ms	1152 KB	Output is correct
28	Correct	10 ms	1280 KB	Output is correct
29	Correct	8 ms	1152 KB	Output is correct
30	Correct	18 ms	1920 KB	Output is correct
31	Correct	19 ms	1920 KB	Output is correct
32	Correct	18 ms	1920 KB	Output is correct
33	Correct	76 ms	8564 KB	Output is correct
34	Correct	74 ms	8624 KB	Output is correct
35	Correct	76 ms	8108 KB	Output is correct
36	Correct	220 ms	16132 KB	Output is correct
37	Correct	213 ms	16264 KB	Output is correct
38	Correct	221 ms	16388 KB	Output is correct
39	Correct	241 ms	13644 KB	Output is correct
40	Correct	242 ms	13628 KB	Output is correct
41	Correct	260 ms	13612 KB	Output is correct
42	Correct	133 ms	15248 KB	Output is correct
43	Correct	238 ms	16004 KB	Output is correct
44	Correct	221 ms	16132 KB	Output is correct
45	Correct	252 ms	16032 KB	Output is correct
46	Correct	264 ms	16052 KB	Output is correct
47	Correct	235 ms	16136 KB	Output is correct
48	Correct	237 ms	16136 KB	Output is correct
49	Correct	265 ms	16132 KB	Output is correct
50	Correct	238 ms	16136 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	0 ms	384 KB	Output is correct
9	Correct	0 ms	384 KB	Output is correct
10	Correct	0 ms	384 KB	Output is correct
11	Correct	0 ms	384 KB	Output is correct
12	Correct	0 ms	384 KB	Output is correct
13	Correct	0 ms	384 KB	Output is correct
14	Correct	1 ms	384 KB	Output is correct
15	Correct	1 ms	384 KB	Output is correct
16	Correct	1 ms	384 KB	Output is correct
17	Correct	1 ms	384 KB	Output is correct
18	Correct	1 ms	384 KB	Output is correct
19	Correct	4 ms	768 KB	Output is correct
20	Correct	4 ms	768 KB	Output is correct
21	Correct	4 ms	768 KB	Output is correct
22	Correct	9 ms	1152 KB	Output is correct
23	Correct	9 ms	1152 KB	Output is correct
24	Correct	9 ms	1152 KB	Output is correct
25	Correct	9 ms	1152 KB	Output is correct
26	Correct	9 ms	1152 KB	Output is correct
27	Correct	212 ms	21440 KB	Output is correct
28	Correct	211 ms	21436 KB	Output is correct
29	Correct	215 ms	22212 KB	Output is correct
30	Correct	211 ms	22064 KB	Output is correct
31	Correct	267 ms	19740 KB	Output is correct
32	Correct	487 ms	32312 KB	Output is correct
33	Correct	291 ms	21380 KB	Output is correct
34	Correct	341 ms	24516 KB	Output is correct
35	Correct	1 ms	384 KB	Output is correct
36	Correct	260 ms	16380 KB	Output is correct
37	Correct	870 ms	49412 KB	Output is correct
38	Correct	823 ms	49544 KB	Output is correct
39	Correct	790 ms	44676 KB	Output is correct
40	Correct	296 ms	22712 KB	Output is correct
41	Correct	125 ms	12164 KB	Output is correct
42	Correct	22 ms	2944 KB	Output is correct
43	Correct	879 ms	48816 KB	Output is correct
44	Correct	796 ms	44216 KB	Output is correct
45	Correct	961 ms	49284 KB	Output is correct
46	Correct	903 ms	48392 KB	Output is correct
47	Correct	332 ms	30600 KB	Output is correct
48	Correct	822 ms	48780 KB	Output is correct
49	Correct	864 ms	49028 KB	Output is correct
50	Correct	260 ms	25976 KB	Output is correct
51	Correct	7 ms	1152 KB	Output is correct
52	Correct	10 ms	1280 KB	Output is correct
53	Correct	8 ms	1152 KB	Output is correct
54	Correct	18 ms	1920 KB	Output is correct
55	Correct	19 ms	1920 KB	Output is correct
56	Correct	18 ms	1920 KB	Output is correct
57	Correct	76 ms	8564 KB	Output is correct
58	Correct	74 ms	8624 KB	Output is correct
59	Correct	76 ms	8108 KB	Output is correct
60	Correct	220 ms	16132 KB	Output is correct
61	Correct	213 ms	16264 KB	Output is correct
62	Correct	221 ms	16388 KB	Output is correct
63	Correct	241 ms	13644 KB	Output is correct
64	Correct	242 ms	13628 KB	Output is correct
65	Correct	260 ms	13612 KB	Output is correct
66	Correct	133 ms	15248 KB	Output is correct
67	Correct	238 ms	16004 KB	Output is correct
68	Correct	221 ms	16132 KB	Output is correct
69	Correct	252 ms	16032 KB	Output is correct
70	Correct	264 ms	16052 KB	Output is correct
71	Correct	235 ms	16136 KB	Output is correct
72	Correct	237 ms	16136 KB	Output is correct
73	Correct	265 ms	16132 KB	Output is correct
74	Correct	238 ms	16136 KB	Output is correct
75	Correct	247 ms	23668 KB	Output is correct
76	Correct	235 ms	23540 KB	Output is correct
77	Correct	237 ms	25196 KB	Output is correct
78	Correct	228 ms	24544 KB	Output is correct
79	Correct	272 ms	23176 KB	Output is correct
80	Correct	229 ms	24656 KB	Output is correct
81	Correct	1055 ms	49424 KB	Output is correct
82	Correct	833 ms	49412 KB	Output is correct
83	Correct	1150 ms	49200 KB	Output is correct
84	Correct	969 ms	49668 KB	Output is correct
85	Correct	983 ms	49284 KB	Output is correct
86	Correct	895 ms	49428 KB	Output is correct
87	Correct	835 ms	49296 KB	Output is correct
88	Correct	881 ms	41356 KB	Output is correct
89	Correct	887 ms	41124 KB	Output is correct
90	Correct	1119 ms	41244 KB	Output is correct
91	Correct	932 ms	41280 KB	Output is correct
92	Correct	881 ms	41108 KB	Output is correct
93	Correct	1104 ms	48264 KB	Output is correct
94	Correct	1056 ms	48644 KB	Output is correct
95	Correct	1062 ms	48264 KB	Output is correct
96	Correct	936 ms	48260 KB	Output is correct
97	Correct	981 ms	48260 KB	Output is correct
98	Correct	705 ms	38840 KB	Output is correct
99	Correct	1032 ms	48644 KB	Output is correct
100	Correct	820 ms	48260 KB	Output is correct
101	Correct	677 ms	43652 KB	Output is correct
102	Correct	805 ms	48036 KB	Output is correct
103	Correct	854 ms	48132 KB	Output is correct
104	Correct	806 ms	48216 KB	Output is correct
105	Correct	504 ms	45956 KB	Output is correct
106	Correct	928 ms	47620 KB	Output is correct
107	Correct	705 ms	47708 KB	Output is correct
108	Correct	741 ms	47496 KB	Output is correct
109	Correct	792 ms	47584 KB	Output is correct
110	Correct	954 ms	47748 KB	Output is correct
111	Correct	958 ms	47632 KB	Output is correct
112	Correct	764 ms	47492 KB	Output is correct
113	Correct	713 ms	47492 KB	Output is correct
114	Correct	1074 ms	47472 KB	Output is correct
115	Correct	701 ms	47620 KB	Output is correct
116	Correct	694 ms	47512 KB	Output is correct

답안 #251488

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