답안 #204943

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
204943	2020-02-27T14:00:17 Z	oolimry	원 고르기 (APIO18_circle_selection)	C++14	100 / 100	1034 ms	49800 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 << 61LL;
 
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	5 ms	376 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	5 ms	388 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	5 ms	376 KB	Output is correct
10	Correct	5 ms	376 KB	Output is correct
11	Correct	6 ms	376 KB	Output is correct
12	Correct	5 ms	376 KB	Output is correct
13	Correct	5 ms	376 KB	Output is correct
14	Correct	5 ms	376 KB	Output is correct
15	Correct	5 ms	376 KB	Output is correct
16	Correct	6 ms	376 KB	Output is correct
17	Correct	5 ms	376 KB	Output is correct
18	Correct	5 ms	376 KB	Output is correct
19	Correct	10 ms	760 KB	Output is correct
20	Correct	9 ms	760 KB	Output is correct
21	Correct	10 ms	760 KB	Output is correct
22	Correct	14 ms	1144 KB	Output is correct
23	Correct	14 ms	1144 KB	Output is correct
24	Correct	13 ms	1144 KB	Output is correct
25	Correct	14 ms	1144 KB	Output is correct
26	Correct	15 ms	1144 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	218 ms	19136 KB	Output is correct
2	Correct	219 ms	19244 KB	Output is correct
3	Correct	215 ms	20036 KB	Output is correct
4	Correct	214 ms	19752 KB	Output is correct
5	Correct	254 ms	19664 KB	Output is correct
6	Correct	535 ms	32184 KB	Output is correct
7	Correct	288 ms	21120 KB	Output is correct
8	Correct	326 ms	24604 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	264 ms	16392 KB	Output is correct
3	Correct	939 ms	45320 KB	Output is correct
4	Correct	956 ms	49528 KB	Output is correct
5	Correct	925 ms	44808 KB	Output is correct
6	Correct	355 ms	22716 KB	Output is correct
7	Correct	156 ms	12296 KB	Output is correct
8	Correct	29 ms	2936 KB	Output is correct
9	Correct	1034 ms	48876 KB	Output is correct
10	Correct	895 ms	44432 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	942 ms	42732 KB	Output is correct
2	Correct	983 ms	45960 KB	Output is correct
3	Correct	400 ms	26624 KB	Output is correct
4	Correct	987 ms	49056 KB	Output is correct
5	Correct	948 ms	49204 KB	Output is correct
6	Correct	280 ms	25976 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	5 ms	388 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	5 ms	376 KB	Output is correct
10	Correct	5 ms	376 KB	Output is correct
11	Correct	6 ms	376 KB	Output is correct
12	Correct	5 ms	376 KB	Output is correct
13	Correct	5 ms	376 KB	Output is correct
14	Correct	5 ms	376 KB	Output is correct
15	Correct	5 ms	376 KB	Output is correct
16	Correct	6 ms	376 KB	Output is correct
17	Correct	5 ms	376 KB	Output is correct
18	Correct	5 ms	376 KB	Output is correct
19	Correct	10 ms	760 KB	Output is correct
20	Correct	9 ms	760 KB	Output is correct
21	Correct	10 ms	760 KB	Output is correct
22	Correct	14 ms	1144 KB	Output is correct
23	Correct	14 ms	1144 KB	Output is correct
24	Correct	13 ms	1144 KB	Output is correct
25	Correct	14 ms	1144 KB	Output is correct
26	Correct	15 ms	1144 KB	Output is correct
27	Correct	12 ms	888 KB	Output is correct
28	Correct	13 ms	888 KB	Output is correct
29	Correct	11 ms	888 KB	Output is correct
30	Correct	23 ms	1656 KB	Output is correct
31	Correct	22 ms	1656 KB	Output is correct
32	Correct	22 ms	1656 KB	Output is correct
33	Correct	80 ms	5492 KB	Output is correct
34	Correct	79 ms	5552 KB	Output is correct
35	Correct	87 ms	5152 KB	Output is correct
36	Correct	253 ms	13700 KB	Output is correct
37	Correct	257 ms	13704 KB	Output is correct
38	Correct	263 ms	13680 KB	Output is correct
39	Correct	273 ms	12584 KB	Output is correct
40	Correct	281 ms	12480 KB	Output is correct
41	Correct	274 ms	12524 KB	Output is correct
42	Correct	149 ms	13576 KB	Output is correct
43	Correct	256 ms	13444 KB	Output is correct
44	Correct	257 ms	13444 KB	Output is correct
45	Correct	262 ms	13448 KB	Output is correct
46	Correct	255 ms	13448 KB	Output is correct
47	Correct	259 ms	13444 KB	Output is correct
48	Correct	254 ms	13548 KB	Output is correct
49	Correct	266 ms	13452 KB	Output is correct
50	Correct	264 ms	13448 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	5 ms	388 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	5 ms	376 KB	Output is correct
10	Correct	5 ms	376 KB	Output is correct
11	Correct	6 ms	376 KB	Output is correct
12	Correct	5 ms	376 KB	Output is correct
13	Correct	5 ms	376 KB	Output is correct
14	Correct	5 ms	376 KB	Output is correct
15	Correct	5 ms	376 KB	Output is correct
16	Correct	6 ms	376 KB	Output is correct
17	Correct	5 ms	376 KB	Output is correct
18	Correct	5 ms	376 KB	Output is correct
19	Correct	10 ms	760 KB	Output is correct
20	Correct	9 ms	760 KB	Output is correct
21	Correct	10 ms	760 KB	Output is correct
22	Correct	14 ms	1144 KB	Output is correct
23	Correct	14 ms	1144 KB	Output is correct
24	Correct	13 ms	1144 KB	Output is correct
25	Correct	14 ms	1144 KB	Output is correct
26	Correct	15 ms	1144 KB	Output is correct
27	Correct	218 ms	19136 KB	Output is correct
28	Correct	219 ms	19244 KB	Output is correct
29	Correct	215 ms	20036 KB	Output is correct
30	Correct	214 ms	19752 KB	Output is correct
31	Correct	254 ms	19664 KB	Output is correct
32	Correct	535 ms	32184 KB	Output is correct
33	Correct	288 ms	21120 KB	Output is correct
34	Correct	326 ms	24604 KB	Output is correct
35	Correct	5 ms	376 KB	Output is correct
36	Correct	264 ms	16392 KB	Output is correct
37	Correct	939 ms	45320 KB	Output is correct
38	Correct	956 ms	49528 KB	Output is correct
39	Correct	925 ms	44808 KB	Output is correct
40	Correct	355 ms	22716 KB	Output is correct
41	Correct	156 ms	12296 KB	Output is correct
42	Correct	29 ms	2936 KB	Output is correct
43	Correct	1034 ms	48876 KB	Output is correct
44	Correct	895 ms	44432 KB	Output is correct
45	Correct	942 ms	42732 KB	Output is correct
46	Correct	983 ms	45960 KB	Output is correct
47	Correct	400 ms	26624 KB	Output is correct
48	Correct	987 ms	49056 KB	Output is correct
49	Correct	948 ms	49204 KB	Output is correct
50	Correct	280 ms	25976 KB	Output is correct
51	Correct	12 ms	888 KB	Output is correct
52	Correct	13 ms	888 KB	Output is correct
53	Correct	11 ms	888 KB	Output is correct
54	Correct	23 ms	1656 KB	Output is correct
55	Correct	22 ms	1656 KB	Output is correct
56	Correct	22 ms	1656 KB	Output is correct
57	Correct	80 ms	5492 KB	Output is correct
58	Correct	79 ms	5552 KB	Output is correct
59	Correct	87 ms	5152 KB	Output is correct
60	Correct	253 ms	13700 KB	Output is correct
61	Correct	257 ms	13704 KB	Output is correct
62	Correct	263 ms	13680 KB	Output is correct
63	Correct	273 ms	12584 KB	Output is correct
64	Correct	281 ms	12480 KB	Output is correct
65	Correct	274 ms	12524 KB	Output is correct
66	Correct	149 ms	13576 KB	Output is correct
67	Correct	256 ms	13444 KB	Output is correct
68	Correct	257 ms	13444 KB	Output is correct
69	Correct	262 ms	13448 KB	Output is correct
70	Correct	255 ms	13448 KB	Output is correct
71	Correct	259 ms	13444 KB	Output is correct
72	Correct	254 ms	13548 KB	Output is correct
73	Correct	266 ms	13452 KB	Output is correct
74	Correct	264 ms	13448 KB	Output is correct
75	Correct	261 ms	23796 KB	Output is correct
76	Correct	247 ms	23756 KB	Output is correct
77	Correct	235 ms	25072 KB	Output is correct
78	Correct	234 ms	24544 KB	Output is correct
79	Correct	287 ms	23288 KB	Output is correct
80	Correct	247 ms	24788 KB	Output is correct
81	Correct	989 ms	49540 KB	Output is correct
82	Correct	951 ms	49412 KB	Output is correct
83	Correct	940 ms	49476 KB	Output is correct
84	Correct	940 ms	49800 KB	Output is correct
85	Correct	969 ms	49284 KB	Output is correct
86	Correct	934 ms	49288 KB	Output is correct
87	Correct	926 ms	49416 KB	Output is correct
88	Correct	980 ms	41464 KB	Output is correct
89	Correct	980 ms	41256 KB	Output is correct
90	Correct	977 ms	41408 KB	Output is correct
91	Correct	977 ms	41424 KB	Output is correct
92	Correct	973 ms	41236 KB	Output is correct
93	Correct	908 ms	48276 KB	Output is correct
94	Correct	920 ms	48520 KB	Output is correct
95	Correct	921 ms	48260 KB	Output is correct
96	Correct	928 ms	48424 KB	Output is correct
97	Correct	915 ms	48260 KB	Output is correct
98	Correct	623 ms	38976 KB	Output is correct
99	Correct	928 ms	48388 KB	Output is correct
100	Correct	906 ms	48560 KB	Output is correct
101	Correct	777 ms	43780 KB	Output is correct
102	Correct	897 ms	48008 KB	Output is correct
103	Correct	921 ms	48004 KB	Output is correct
104	Correct	948 ms	48092 KB	Output is correct
105	Correct	595 ms	45960 KB	Output is correct
106	Correct	799 ms	47624 KB	Output is correct
107	Correct	802 ms	47624 KB	Output is correct
108	Correct	802 ms	47620 KB	Output is correct
109	Correct	813 ms	47612 KB	Output is correct
110	Correct	811 ms	47628 KB	Output is correct
111	Correct	808 ms	47624 KB	Output is correct
112	Correct	785 ms	47492 KB	Output is correct
113	Correct	800 ms	47620 KB	Output is correct
114	Correct	892 ms	47660 KB	Output is correct
115	Correct	825 ms	47748 KB	Output is correct
116	Correct	811 ms	47624 KB	Output is correct

답안 #204943

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