oj.uz

Submission #221320

# Submission time Handle Problem Language Result Execution time Memory
221320 2020-04-09T21:28:50 Z Bruteforceman Circle selection (APIO18_circle_selection) C++11
0 / 100
 1278 ms 67960 KB 
#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);
    		// cout << i.idx << ' ' << i.x / block << ' ' << i.y / block << endl; 
     	}
    };
    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);
    };
    while(!s.empty()) {
    	if(s.begin() -> r * 2 < block) {
    		rebuild(s.begin() -> r + 1);
    	}
    	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;
    			if(cont.find(pii(dx, dy)) == cont.end()) continue;
    			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.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Incorrect 5 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 34168 KB Output is correct
2 Incorrect 517 ms 34324 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1278 ms 67960 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Incorrect 5 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Incorrect 5 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -