Submission #243925

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
243925	2020-07-02T08:40:41 Z	atoiz	Circle selection (APIO18_circle_selection)	C++14	75 / 100	999 ms	40184 KB

circle_selection

// https://oj.uz/submission/77965

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

const double INF = 1e9, EPS = 1e-8;

double sqr(double x) { return x * x; }
void minimize(double &x, double y) { x = (x < y ? x : y); }
void maximize(double &x, double y) { x = (x > y ? x : y); }

struct Box
{
	double x0, x1, y0, y1;
	Box(double _x0 = INF, double _x1 = -INF, double _y0 = INF, double _y1 = -INF): x0(_x0), x1(_x1), y0(_y0), y1(_y1) {}
	bool intersect(const Box &b) const { return (x0 < b.x1 + EPS && b.x0 < x1 + EPS && y0 < b.y1 + EPS && b.y0 < y1 + EPS); }
	void expand(const Box &b) { minimize(x0, b.x0), minimize(y0, b.y0), maximize(x1, b.x1), maximize(y1, b.y1); }
};

struct Circle
{
	double x, y, r;
	int i;
	bool intersect(const Circle &c) const { return sqr(c.x - x) + sqr(c.y - y) < sqr(r + c.r) + EPS; }
	Box toBox() { return Box(x - r, x + r, y - r, y + r); }
};

bool compX(const Circle &a, const Circle &b) { return (abs(a.x - b.x) < EPS ? (a.y < b.y) : (a.x < b.x)); }
bool compY(const Circle &a, const Circle &b) { return (abs(a.y - b.y) < EPS ? (a.x < b.x) : (a.y < b.y)); }
bool compR(const Circle &a, const Circle &b) { return (abs(a.r - b.r) < EPS ? (a.i < b.i) : (a.r > b.r)); }

int n;
vector<int> ans;
vector<Circle> circles, cirTree;
vector<Box> boxTree;

void build(int lo = 0, int hi = n - 1, bool byX = 0)
{
	int mid = (lo + hi) >> 1;
	nth_element(cirTree.begin() + lo, cirTree.begin() + mid, cirTree.begin() + hi + 1, (byX ? compX : compY));
	boxTree[mid] = cirTree[mid].toBox();

	if (lo < mid) {
		build(lo, mid - 1, !byX);
		boxTree[mid].expand(boxTree[(lo + mid - 1) >> 1]);
	}

	if (mid < hi) {
		build(mid + 1, hi, !byX);
		boxTree[mid].expand(boxTree[(mid + 1 + hi) >> 1]);
	}

	// cout << mid << ' ' << lo << ' ' << hi << ' ' << cirTree[mid].i << ": ";
	// cout << boxTree[mid].x0 << ' ' << boxTree[mid].x1 << ' ' << boxTree[mid].y0 << ' ' << boxTree[mid].y1 << endl;
}

void get(Circle &c, Box &b, int lo = 0, int hi = n - 1, bool byX = 0)
{
	int mid = (lo + hi) >> 1;
	if (ans[cirTree[mid].i] == -1 && cirTree[mid].intersect(c)) ans[cirTree[mid].i] = c.i;
	// cout << c.i << ": " << lo << ' ' << hi << ' ' << cirTree[mid].i << " - ";
	// cout << boxTree[mid].x0 << ' ' << boxTree[mid].x1 << ' ' << boxTree[mid].y0 << ' ' << boxTree[mid].y1 << endl;

	boxTree[mid] = Box(INF, -INF, INF, -INF);
	if (ans[cirTree[mid].i] == -1) boxTree[mid] = cirTree[mid].toBox();
	int lc = (lo + mid - 1) >> 1, rc = (mid + 1 + hi) >> 1;
	if (lo < mid) {
		if (boxTree[lc].intersect(b)) get(c, b, lo, mid - 1, !byX);
		boxTree[mid].expand(boxTree[lc]);
	}
	if (mid < hi) {
		if (boxTree[rc].intersect(b)) get(c, b, mid + 1, hi, !byX);
		boxTree[mid].expand(boxTree[rc]);
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	circles.resize(n);
	for (int i = 0; i < n; ++i) {
		cin >> circles[i].x >> circles[i].y >> circles[i].r;
		circles[i].i = i;
	}
	sort(circles.begin(), circles.end(), compR);

	cirTree = circles;
	boxTree.resize(n);
	ans.assign(n, -1);
	build();

	for (auto &c : circles) if (ans[c.i] == -1) {
		ans[c.i] = c.i;
		Box b = c.toBox();
		get(c, b);
	}
	for (int i = 0; i < n; ++i) cout << ans[i] + 1 << ' ';
}

Subtask #1
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	388 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Correct	5 ms	384 KB	Output is correct
12	Correct	5 ms	384 KB	Output is correct
13	Correct	5 ms	384 KB	Output is correct
14	Correct	5 ms	384 KB	Output is correct
15	Correct	5 ms	384 KB	Output is correct
16	Correct	6 ms	512 KB	Output is correct
17	Correct	6 ms	512 KB	Output is correct
18	Correct	7 ms	512 KB	Output is correct
19	Correct	13 ms	1024 KB	Output is correct
20	Correct	13 ms	1024 KB	Output is correct
21	Correct	13 ms	1024 KB	Output is correct
22	Correct	16 ms	1024 KB	Output is correct
23	Correct	15 ms	1024 KB	Output is correct
24	Correct	14 ms	1024 KB	Output is correct
25	Correct	15 ms	1024 KB	Output is correct
26	Correct	15 ms	1024 KB	Output is correct

Subtask #2
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	520 ms	38664 KB	Output is correct
2	Correct	470 ms	38648 KB	Output is correct
3	Correct	460 ms	38228 KB	Output is correct
4	Correct	473 ms	38572 KB	Output is correct
5	Incorrect	443 ms	36344 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #3
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	284 ms	13480 KB	Output is correct
3	Correct	879 ms	39932 KB	Output is correct
4	Correct	999 ms	39928 KB	Output is correct
5	Correct	779 ms	38904 KB	Output is correct
6	Correct	354 ms	20984 KB	Output is correct
7	Correct	171 ms	11128 KB	Output is correct
8	Correct	36 ms	2552 KB	Output is correct
9	Correct	886 ms	39928 KB	Output is correct
10	Correct	724 ms	40184 KB	Output is correct

Subtask #4
23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	879 ms	39592 KB	Output is correct
2	Correct	902 ms	38904 KB	Output is correct
3	Correct	563 ms	39800 KB	Output is correct
4	Correct	871 ms	39288 KB	Output is correct
5	Correct	871 ms	39288 KB	Output is correct
6	Correct	538 ms	39672 KB	Output is correct

Subtask #5
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	388 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Correct	5 ms	384 KB	Output is correct
12	Correct	5 ms	384 KB	Output is correct
13	Correct	5 ms	384 KB	Output is correct
14	Correct	5 ms	384 KB	Output is correct
15	Correct	5 ms	384 KB	Output is correct
16	Correct	6 ms	512 KB	Output is correct
17	Correct	6 ms	512 KB	Output is correct
18	Correct	7 ms	512 KB	Output is correct
19	Correct	13 ms	1024 KB	Output is correct
20	Correct	13 ms	1024 KB	Output is correct
21	Correct	13 ms	1024 KB	Output is correct
22	Correct	16 ms	1024 KB	Output is correct
23	Correct	15 ms	1024 KB	Output is correct
24	Correct	14 ms	1024 KB	Output is correct
25	Correct	15 ms	1024 KB	Output is correct
26	Correct	15 ms	1024 KB	Output is correct
27	Correct	24 ms	1664 KB	Output is correct
28	Correct	21 ms	1784 KB	Output is correct
29	Correct	21 ms	1664 KB	Output is correct
30	Correct	24 ms	1664 KB	Output is correct
31	Correct	24 ms	1664 KB	Output is correct
32	Correct	25 ms	1664 KB	Output is correct
33	Correct	178 ms	13816 KB	Output is correct
34	Correct	178 ms	13944 KB	Output is correct
35	Correct	181 ms	13688 KB	Output is correct
36	Correct	236 ms	13304 KB	Output is correct
37	Correct	250 ms	13432 KB	Output is correct
38	Correct	242 ms	13432 KB	Output is correct
39	Correct	192 ms	11768 KB	Output is correct
40	Correct	191 ms	11768 KB	Output is correct
41	Correct	192 ms	11768 KB	Output is correct
42	Correct	165 ms	12280 KB	Output is correct
43	Correct	212 ms	13304 KB	Output is correct
44	Correct	222 ms	13304 KB	Output is correct
45	Correct	215 ms	13432 KB	Output is correct
46	Correct	215 ms	13304 KB	Output is correct
47	Correct	210 ms	13432 KB	Output is correct
48	Correct	217 ms	13432 KB	Output is correct
49	Correct	210 ms	13304 KB	Output is correct
50	Correct	209 ms	13304 KB	Output is correct

Subtask #6
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	388 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Correct	5 ms	384 KB	Output is correct
12	Correct	5 ms	384 KB	Output is correct
13	Correct	5 ms	384 KB	Output is correct
14	Correct	5 ms	384 KB	Output is correct
15	Correct	5 ms	384 KB	Output is correct
16	Correct	6 ms	512 KB	Output is correct
17	Correct	6 ms	512 KB	Output is correct
18	Correct	7 ms	512 KB	Output is correct
19	Correct	13 ms	1024 KB	Output is correct
20	Correct	13 ms	1024 KB	Output is correct
21	Correct	13 ms	1024 KB	Output is correct
22	Correct	16 ms	1024 KB	Output is correct
23	Correct	15 ms	1024 KB	Output is correct
24	Correct	14 ms	1024 KB	Output is correct
25	Correct	15 ms	1024 KB	Output is correct
26	Correct	15 ms	1024 KB	Output is correct
27	Correct	520 ms	38664 KB	Output is correct
28	Correct	470 ms	38648 KB	Output is correct
29	Correct	460 ms	38228 KB	Output is correct
30	Correct	473 ms	38572 KB	Output is correct
31	Incorrect	443 ms	36344 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

Submission #243925

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 0 / 12.0

Subtask #3 15.0 / 15.0

Subtask #4 23.0 / 23.0

Subtask #5 30.0 / 30.0

Subtask #6 0 / 13.0

Subtask #1
7.0 / 7.0

Subtask #2
0 / 12.0

Subtask #3
15.0 / 15.0

Subtask #4
23.0 / 23.0

Subtask #5
30.0 / 30.0

Subtask #6
0 / 13.0