oj.uz

Submission #221325

# Submission time Handle Problem Language Result Execution time Memory
221325 2020-04-09T21:40:00 Z Bruteforceman Circle selection (APIO18_circle_selection) C++11
0 / 100
 3000 ms 233756 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair <int, int>;
const int maxn = 300005;
struct data {
    long long 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;
    long long block;
    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 + 1); 
    while(!s.empty()) {
    	if(4LL * s.begin() -> r < block) {
    		rebuild(s.begin() -> r * 2 + 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;
    			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 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Incorrect 5 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 36684 KB Output is correct
2 Incorrect 546 ms 36752 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 756 ms 49556 KB Output is correct
3 Correct 2781 ms 150264 KB Output is correct
4 Correct 2780 ms 150664 KB Output is correct
5 Correct 2641 ms 92256 KB Output is correct
6 Correct 957 ms 46232 KB Output is correct
7 Correct 393 ms 23676 KB Output is correct
8 Correct 49 ms 6392 KB Output is correct
9 Execution timed out 3091 ms 111636 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2291 ms 233696 KB Output is correct
2 Correct 1816 ms 233756 KB Output is correct
3 Incorrect 840 ms 40824 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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

Subtask #6
0 / 13.0

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