Submission #221324

#	Time	Username	Problem	Language	Result	Execution time	Memory
221324		Bruteforceman	Circle selection (APIO18_circle_selection)	C++11	0 / 100	3099 ms	236172 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;
using pii = pair <int, int>;
const int maxn = 300005;
struct data {
    int x, y, r, idx;
    bool operator < (data p) const {
        return make_pair(r, -idx) > make_pair(p.r, -p.idx);
    }
} a[maxn];
int c[maxn];

int main() {
	ios_base :: sync_with_stdio (false);
	cin.tie(0);
    int n; 
    cin >> n;
    set <data> s;
    const int shift = 1000000007;
    for(int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].y >> a[i].r;
        a[i].idx = i;
        a[i].x += shift; a[i].y += shift;
    	s.insert(a[i]);
    }   
    map <pii, vector <int>> cont;
    int block = INT_MAX;
    function <void(int)> rebuild = [&] (int bs) {
    	block = bs;
    	cont.clear();
    	for(auto i : s) {
    		cont[pii(i.x / block, i.y / block)].push_back(i.idx);
     	}
    };
    function <bool(int, int)> reach = [&] (int i, int j) {
    	auto square = [] (long long x) { return x * x; };
    	return square(a[i].x - a[j].x) + square(a[i].y - a[j].y) <= square(a[i].r + a[j].r);
    };
    rebuild(s.begin() -> r * 2); 
    while(!s.empty()) {
    	if(4LL * s.begin() -> r < block) {
    		rebuild(s.begin() -> r * 2);
    	}
    	data d = *s.begin();
    	int bx = d.x / block;
    	int by = d.y / block;
    	for(int i : {-1, 0, 1}) {
    		for(int j : {-1, 0, 1}) {
    			int dx = bx + i;
    			int dy = by + j;
    			for(auto k : cont[pii(dx, dy)]) {
    				if(reach(k, d.idx)) {
						s.erase(a[k]);    					
    					c[k] = d.idx;
    				}
    			} 
    		}
    	}
    }
    for(int i = 1; i <= n; i++) {
    	cout << c[i] << " \n"[i == n];
    }
    return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13