oj.uz

Submission #204942

# Submission time Handle Problem Language Result Execution time Memory
204942 2020-02-27T13:57:43 Z oolimry Circle selection (APIO18_circle_selection) C++14
49 / 100
 3000 ms 446604 KB 
#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")

using namespace std; 
int n; 
 
struct Circle{
	long long x, y, r, id;
} sorted[300005], arr[300005];;
 
inline 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);
}
 
inline long long ii(long long a, long long b){
	return a * (1LL << 32LL) + b;
}
long long ans[300005];

unordered_map<long long, vector<int> > GRID;
long long gridSize = 1LL << 61LL;
 
inline 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;
				
		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 << " ";
}

Compilation message

circle_selection.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("Ofast")
 
circle_selection.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory 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 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 5 ms 504 KB Output is correct
12 Correct 5 ms 508 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 6 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 10 ms 888 KB Output is correct
21 Correct 8 ms 888 KB Output is correct
22 Correct 26 ms 5000 KB Output is correct
23 Correct 26 ms 4872 KB Output is correct
24 Correct 25 ms 4872 KB Output is correct
25 Correct 28 ms 5000 KB Output is correct
26 Correct 26 ms 5068 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 25556 KB Output is correct
2 Correct 213 ms 25224 KB Output is correct
3 Correct 212 ms 26300 KB Output is correct
4 Correct 229 ms 25152 KB Output is correct
5 Correct 249 ms 28740 KB Output is correct
6 Correct 1258 ms 78340 KB Output is correct
7 Correct 313 ms 32132 KB Output is correct
8 Correct 462 ms 39588 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 1027 ms 86824 KB Output is correct
3 Execution timed out 3081 ms 295412 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 3056 ms 446604 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 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 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 5 ms 504 KB Output is correct
12 Correct 5 ms 508 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 6 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 10 ms 888 KB Output is correct
21 Correct 8 ms 888 KB Output is correct
22 Correct 26 ms 5000 KB Output is correct
23 Correct 26 ms 4872 KB Output is correct
24 Correct 25 ms 4872 KB Output is correct
25 Correct 28 ms 5000 KB Output is correct
26 Correct 26 ms 5068 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 1528 KB Output is correct
30 Correct 70 ms 9504 KB Output is correct
31 Correct 59 ms 9528 KB Output is correct
32 Correct 73 ms 9548 KB Output is correct
33 Correct 86 ms 11764 KB Output is correct
34 Correct 84 ms 11636 KB Output is correct
35 Correct 87 ms 11176 KB Output is correct
36 Correct 1043 ms 89424 KB Output is correct
37 Correct 1038 ms 89168 KB Output is correct
38 Correct 1047 ms 89148 KB Output is correct
39 Correct 367 ms 30068 KB Output is correct
40 Correct 365 ms 30128 KB Output is correct
41 Correct 363 ms 30212 KB Output is correct
42 Correct 153 ms 18444 KB Output is correct
43 Correct 1171 ms 145092 KB Output is correct
44 Correct 1359 ms 145092 KB Output is correct
45 Correct 1569 ms 145056 KB Output is correct
46 Correct 1079 ms 145380 KB Output is correct
47 Correct 1057 ms 145508 KB Output is correct
48 Correct 1069 ms 145348 KB Output is correct
49 Correct 1076 ms 145616 KB Output is correct
50 Correct 1068 ms 145204 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 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 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 5 ms 504 KB Output is correct
12 Correct 5 ms 508 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 6 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 10 ms 888 KB Output is correct
21 Correct 8 ms 888 KB Output is correct
22 Correct 26 ms 5000 KB Output is correct
23 Correct 26 ms 4872 KB Output is correct
24 Correct 25 ms 4872 KB Output is correct
25 Correct 28 ms 5000 KB Output is correct
26 Correct 26 ms 5068 KB Output is correct
27 Correct 229 ms 25556 KB Output is correct
28 Correct 213 ms 25224 KB Output is correct
29 Correct 212 ms 26300 KB Output is correct
30 Correct 229 ms 25152 KB Output is correct
31 Correct 249 ms 28740 KB Output is correct
32 Correct 1258 ms 78340 KB Output is correct
33 Correct 313 ms 32132 KB Output is correct
34 Correct 462 ms 39588 KB Output is correct
35 Correct 5 ms 376 KB Output is correct
36 Correct 1027 ms 86824 KB Output is correct
37 Execution timed out 3081 ms 295412 KB Time limit exceeded
38 Halted 0 ms 0 KB -