oj.uz

Submission #387637

# Submission time Handle Problem Language Result Execution time Memory
387637 2021-04-09T04:48:06 Z milleniumEeee Circle selection (APIO18_circle_selection) C++17
7 / 100
 282 ms 34628 KB 
#include <bits/stdc++.h>
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
#define pii pair<int, int>
#define fr first
#define sc second
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define mk make_pair
#define int long long
using namespace std;

const int MAXN = (int)3e5 + 5;

int n;

int x[MAXN];
int y[MAXN];
int rad[MAXN];

vector <int> g[MAXN];

double get_dist(int i, int j) {
	return (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
}

bool intersect(int i, int j) {
	return (get_dist(i, j) <= (rad[i] + rad[j]) * (rad[i] + rad[j]));
}

int ans[MAXN];

vector <int> pos;

void subtask1() {
	for (int i = 0; i < n; i++) {
		pos.pb(i);
	}
	sort(all(pos), [&](int A, int B) {
		if (rad[A] != rad[B]) {
			return rad[A] > rad[B];
		} else {
			return A < B;
		}
	});
	memset(ans, -1, sizeof(ans));
	for (int el : pos) {
		if (ans[el] == -1) {
			ans[el] = el;
			for (int i = 0; i < n; i++) {
				if (ans[i] == -1 && intersect(i, el)) {
					ans[i] = el;
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		cout << ans[i] + 1 << " ";
	}
	exit(0);
}

struct node {
	int x, y, rad;
	int ind;
	node () {
		
	}
	node (int x_, int y_, int rad_, int ind_) {
		x = x_;
		y = y_;
		rad = rad_;
		ind = ind_;
	}
	const bool operator < (const node &other) {
		return x < other.x;
	}
};

signed main() {
	fastInp;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> y[i] >> rad[i];
	}
	if (n <= 5000) {
		subtask1();
	}
	else {
		vector <node> vec;
		for (int i = 0; i < n; i++) {
			vec.pb(node(x[i], y[i], rad[i], i));
		}
		sort(all(vec));
		for (int i = 0; i < n; i++) {
			pos.pb(i);
		}
		sort(all(pos), [&](int A, int B) {
			if (vec[A].rad != vec[B].rad) {
				return vec[A].rad > vec[B].rad;
			} else {
				return vec[A].ind < vec[B].ind;
			}
		});
		memset(ans, -1, sizeof(ans));
		vector <int> block(1000, -1);
		int S = sqrt(n);
		if (S * S < n) {
			S++;
		}
		for (int order : pos) {
			if (ans[vec[order].ind] != -1) {
				continue;
			}
			if (block[order / S] != -1) {
				continue;
			}
			int x = vec[order].x;
			int rad = vec[order].rad;
			int lp = x - rad;
			int rp = x + rad;
			int l = -1, r = order;
			int lft, rgt;
			while (r - l > 1) {
				int mid = (l + r) >> 1;
				if (vec[mid].x >= lp) {
					r = mid;
				} else {
					l = mid;
				}
			}
			lft = r;
			l = order, r = n; // 0-index
			while (r - l > 1) {
				int mid = (l + r) >> 1;
				if (vec[mid].x <= rp) {
					l = mid;
				} else {
					r = mid;
				}
			}
			rgt = l;
			// update in sqrt decomposition 
			if (lft % S != 0) {
				for (int j = lft; j < (lft / S + 1) * S; j++) {
					if (block[j / S] != -1 || ans[vec[j].ind] != -1) {
						continue;
					}
					ans[vec[j].ind] = vec[order].ind;
				}
			}
			if ((rgt + 1) % S != 0) {
				for (int j = rgt; j >= (rgt / S) * S; j--) {
					if (block[j / S] != -1 || ans[vec[j].ind] != -1) {
						continue;
					}
					ans[vec[j].ind] = vec[order].ind;
				}
			}
			int l_block = (lft % S != 0 ? lft / S + 1 : lft / S);
			int r_block = ((rgt + 1) % S != 0 ? rgt / S - 1 : rgt / S);
			for (int j = l_block; j <= r_block; j++) {
				if (block[j] == -1) {
					block[j] = vec[order].ind;
				}
			}
		}
		for (int i = 0; i < n; i++) {
			if (ans[i] != -1) {
				cout << ans[i] + 1 << " ";
			} else {
				cout << block[i / S] + 1 << " ";
			}
		}
	}
}
/*
11
9 9 2
13 2 1
11 8 2 
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2 
5 2 1
14 4 2
14 14 1
*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9616 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 6 ms 9676 KB Output is correct
10 Correct 6 ms 9676 KB Output is correct
11 Correct 6 ms 9676 KB Output is correct
12 Correct 6 ms 9676 KB Output is correct
13 Correct 6 ms 9676 KB Output is correct
14 Correct 6 ms 9724 KB Output is correct
15 Correct 6 ms 9676 KB Output is correct
16 Correct 6 ms 9676 KB Output is correct
17 Correct 7 ms 9676 KB Output is correct
18 Correct 6 ms 9772 KB Output is correct
19 Correct 8 ms 9932 KB Output is correct
20 Correct 8 ms 9932 KB Output is correct
21 Correct 9 ms 9932 KB Output is correct
22 Correct 71 ms 9932 KB Output is correct
23 Correct 72 ms 9936 KB Output is correct
24 Correct 73 ms 9928 KB Output is correct
25 Correct 72 ms 9932 KB Output is correct
26 Correct 72 ms 9932 KB Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Incorrect 78 ms 17584 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9616 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 6 ms 9676 KB Output is correct
10 Correct 6 ms 9676 KB Output is correct
11 Correct 6 ms 9676 KB Output is correct
12 Correct 6 ms 9676 KB Output is correct
13 Correct 6 ms 9676 KB Output is correct
14 Correct 6 ms 9724 KB Output is correct
15 Correct 6 ms 9676 KB Output is correct
16 Correct 6 ms 9676 KB Output is correct
17 Correct 7 ms 9676 KB Output is correct
18 Correct 6 ms 9772 KB Output is correct
19 Correct 8 ms 9932 KB Output is correct
20 Correct 8 ms 9932 KB Output is correct
21 Correct 9 ms 9932 KB Output is correct
22 Correct 71 ms 9932 KB Output is correct
23 Correct 72 ms 9936 KB Output is correct
24 Correct 73 ms 9928 KB Output is correct
25 Correct 72 ms 9932 KB Output is correct
26 Correct 72 ms 9932 KB Output is correct
27 Incorrect 13 ms 10524 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9616 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 6 ms 9676 KB Output is correct
10 Correct 6 ms 9676 KB Output is correct
11 Correct 6 ms 9676 KB Output is correct
12 Correct 6 ms 9676 KB Output is correct
13 Correct 6 ms 9676 KB Output is correct
14 Correct 6 ms 9724 KB Output is correct
15 Correct 6 ms 9676 KB Output is correct
16 Correct 6 ms 9676 KB Output is correct
17 Correct 7 ms 9676 KB Output is correct
18 Correct 6 ms 9772 KB Output is correct
19 Correct 8 ms 9932 KB Output is correct
20 Correct 8 ms 9932 KB Output is correct
21 Correct 9 ms 9932 KB Output is correct
22 Correct 71 ms 9932 KB Output is correct
23 Correct 72 ms 9936 KB Output is correct
24 Correct 73 ms 9928 KB Output is correct
25 Correct 72 ms 9932 KB Output is correct
26 Correct 72 ms 9932 KB Output is correct
27 Incorrect 248 ms 34628 KB Output isn't correct
28 Halted 0 ms 0 KB -