oj.uz

Submission #204937

# Submission time Handle Problem Language Result Execution time Memory
204937 2020-02-27T13:44:22 Z oolimry Circle selection (APIO18_circle_selection) C++14
49 / 100
 3000 ms 513768 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -