oj.uz

Submission #204928

# Submission time Handle Problem Language Result Execution time Memory
204928 2020-02-27T13:10:16 Z oolimry Circle selection (APIO18_circle_selection) C++14
12 / 100
 3000 ms 294596 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;
	}
};

unordered_map<ii, vector<int>, pair_hash> 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
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 388 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Incorrect 5 ms 380 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 30820 KB Output is correct
2 Correct 222 ms 30472 KB Output is correct
3 Correct 215 ms 31676 KB Output is correct
4 Correct 219 ms 30528 KB Output is correct
5 Correct 248 ms 32040 KB Output is correct
6 Correct 974 ms 84332 KB Output is correct
7 Correct 298 ms 35844 KB Output is correct
8 Correct 397 ms 43448 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 Execution timed out 3066 ms 92512 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3108 ms 294596 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
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 388 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Incorrect 5 ms 380 KB Output isn't correct
9 Halted 0 ms 0 KB -

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 388 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Incorrect 5 ms 380 KB Output isn't correct
9 Halted 0 ms 0 KB -