답안 #204937

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
204937	2020-02-27T13:44:22 Z	oolimry	원 고르기 (APIO18_circle_selection)	C++14	49 / 100	3000 ms	513768 KB

circle_selection

#include <bits/stdc++.h>
 
using namespace std;
typedef pair<long long, long long> ii;
 
int n; 
 
struct Circle{
	long long x, y, r, id;
} sorted[300005], 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];
 
struct pair_hash{
	std::size_t operator () (ii const &pair) const{
		return pair.first ^ pair.second;
	}
};
 
map<ii, 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(ans[i] == -1){
			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 << 31LL); y += (1LL << 31LL);
		arr[i] = {x, y, r, i};
		sorted[i] = {x, y, r, i};
	}
	
	sort(sorted,sorted+n,comp);
	
	for(int i = 0;i < n;i++){
		Circle C = sorted[i];
		
		if(ans[C.id] != -1) continue;
		ans[C.id] = C.id;
		
		if(gridSize > 2 * 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++){
				vector<int> &points = GRID[ii(x,y)];
				
				for(int p = 0;p < (int) points.size();p++){
					if(intersect(arr[points[p]],C)){
						ans[points[p]] = C.id;
												
						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	6 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	380 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	5 ms	376 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	7 ms	504 KB	Output is correct
12	Correct	5 ms	504 KB	Output is correct
13	Correct	6 ms	504 KB	Output is correct
14	Correct	5 ms	504 KB	Output is correct
15	Correct	5 ms	376 KB	Output is correct
16	Correct	6 ms	504 KB	Output is correct
17	Correct	6 ms	504 KB	Output is correct
18	Correct	5 ms	504 KB	Output is correct
19	Correct	9 ms	888 KB	Output is correct
20	Correct	9 ms	888 KB	Output is correct
21	Correct	9 ms	888 KB	Output is correct
22	Correct	41 ms	6136 KB	Output is correct
23	Correct	45 ms	6136 KB	Output is correct
24	Correct	41 ms	6160 KB	Output is correct
25	Correct	42 ms	6136 KB	Output is correct
26	Correct	42 ms	6140 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	222 ms	25024 KB	Output is correct
2	Correct	211 ms	24584 KB	Output is correct
3	Correct	212 ms	25660 KB	Output is correct
4	Correct	214 ms	24528 KB	Output is correct
5	Correct	296 ms	28688 KB	Output is correct
6	Correct	1325 ms	98296 KB	Output is correct
7	Correct	369 ms	31356 KB	Output is correct
8	Correct	550 ms	43896 KB	Output is correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	1408 ms	111864 KB	Output is correct
3	Execution timed out	3098 ms	334328 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	3109 ms	513768 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	6 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	380 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	5 ms	376 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	7 ms	504 KB	Output is correct
12	Correct	5 ms	504 KB	Output is correct
13	Correct	6 ms	504 KB	Output is correct
14	Correct	5 ms	504 KB	Output is correct
15	Correct	5 ms	376 KB	Output is correct
16	Correct	6 ms	504 KB	Output is correct
17	Correct	6 ms	504 KB	Output is correct
18	Correct	5 ms	504 KB	Output is correct
19	Correct	9 ms	888 KB	Output is correct
20	Correct	9 ms	888 KB	Output is correct
21	Correct	9 ms	888 KB	Output is correct
22	Correct	41 ms	6136 KB	Output is correct
23	Correct	45 ms	6136 KB	Output is correct
24	Correct	41 ms	6160 KB	Output is correct
25	Correct	42 ms	6136 KB	Output is correct
26	Correct	42 ms	6140 KB	Output is correct
27	Correct	12 ms	1528 KB	Output is correct
28	Correct	12 ms	1528 KB	Output is correct
29	Correct	12 ms	1404 KB	Output is correct
30	Correct	91 ms	11844 KB	Output is correct
31	Correct	85 ms	11896 KB	Output is correct
32	Correct	89 ms	12024 KB	Output is correct
33	Correct	97 ms	9588 KB	Output is correct
34	Correct	79 ms	9588 KB	Output is correct
35	Correct	91 ms	9280 KB	Output is correct
36	Correct	1270 ms	114424 KB	Output is correct
37	Correct	1268 ms	114040 KB	Output is correct
38	Correct	1332 ms	113668 KB	Output is correct
39	Correct	490 ms	36476 KB	Output is correct
40	Correct	505 ms	36392 KB	Output is correct
41	Correct	498 ms	36684 KB	Output is correct
42	Correct	282 ms	20988 KB	Output is correct
43	Correct	937 ms	184056 KB	Output is correct
44	Correct	928 ms	184312 KB	Output is correct
45	Correct	928 ms	184128 KB	Output is correct
46	Correct	928 ms	184440 KB	Output is correct
47	Correct	934 ms	184568 KB	Output is correct
48	Correct	921 ms	184440 KB	Output is correct
49	Correct	931 ms	184696 KB	Output is correct
50	Correct	932 ms	184312 KB	Output is correct

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	6 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	380 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	5 ms	376 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	7 ms	504 KB	Output is correct
12	Correct	5 ms	504 KB	Output is correct
13	Correct	6 ms	504 KB	Output is correct
14	Correct	5 ms	504 KB	Output is correct
15	Correct	5 ms	376 KB	Output is correct
16	Correct	6 ms	504 KB	Output is correct
17	Correct	6 ms	504 KB	Output is correct
18	Correct	5 ms	504 KB	Output is correct
19	Correct	9 ms	888 KB	Output is correct
20	Correct	9 ms	888 KB	Output is correct
21	Correct	9 ms	888 KB	Output is correct
22	Correct	41 ms	6136 KB	Output is correct
23	Correct	45 ms	6136 KB	Output is correct
24	Correct	41 ms	6160 KB	Output is correct
25	Correct	42 ms	6136 KB	Output is correct
26	Correct	42 ms	6140 KB	Output is correct
27	Correct	222 ms	25024 KB	Output is correct
28	Correct	211 ms	24584 KB	Output is correct
29	Correct	212 ms	25660 KB	Output is correct
30	Correct	214 ms	24528 KB	Output is correct
31	Correct	296 ms	28688 KB	Output is correct
32	Correct	1325 ms	98296 KB	Output is correct
33	Correct	369 ms	31356 KB	Output is correct
34	Correct	550 ms	43896 KB	Output is correct
35	Correct	5 ms	376 KB	Output is correct
36	Correct	1408 ms	111864 KB	Output is correct
37	Execution timed out	3098 ms	334328 KB	Time limit exceeded
38	Halted	0 ms	0 KB	-

답안 #204937

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 12.0 / 12.0

Subtask #3 0 / 15.0

Subtask #4 0 / 23.0

Subtask #5 30.0 / 30.0

Subtask #6 0 / 13.0

Subtask #1
7.0 / 7.0

Subtask #2
12.0 / 12.0

Subtask #3
0 / 15.0

Subtask #4
0 / 23.0

Subtask #5
30.0 / 30.0

Subtask #6
0 / 13.0