Submission #243432

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
243432	2020-07-01T06:42:16 Z	atoiz	Circle selection (APIO18_circle_selection)	C++14	64 / 100	3000 ms	48204 KB

circle_selection

/*input
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
*/

// spoiled

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <random>
#include <chrono>
#include <unordered_map>

using namespace std;

mt19937 rng(chrono::system_clock().now().time_since_epoch().count());

inline long long sqr(int x) { return (long long) x * x; }

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

const int OFFSET = 1000 * 1000 * 1000;
int N;
vector<Circle> cir;
vector<int> ans;
unordered_map<long long, vector<int>> grid;

inline long long hsh(int x, int y) { return (((long long) x) << 30 ^ y); }

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	// N = 300000;
	ans.assign(N, -1);
	cir.resize(N);
	for (int i = 0; i < N; ++i) {
		cin >> cir[i].x >> cir[i].y >> cir[i].r;
		// cir[i].x = rng() % OFFSET, cir[i].y = rng() % OFFSET, cir[i].r = exp(1.0 * rng() / mt19937::max() * log(10000));
		cir[i].x += OFFSET;
		cir[i].y += OFFSET;
		cir[i].i = i;
	}

	auto vec = cir;
	sort(vec.begin(), vec.end(), [&](Circle &a, Circle &b) {
		return (a.r == b.r ? (a.i < b.i) : (a.r > b.r));
	});

	auto c = vec.begin();

	for (int i = 30; i >= 0; --i) {
		grid.clear();
		for (auto t : vec) if (!~ans[t.i]) {
			grid[hsh(t.x >> i, t.y >> i)].push_back(t.i);
		}

		for (; c != vec.end() && c->r > ((1 << i) >> 1); ++c) if (!~ans[c->i]) {
			int cx = c->x >> i, cy = c->y >> i;
			for (int tx = cx - 2; tx <= cx + 2; ++tx) {
				for (int ty = cy - 2; ty <= cy + 2; ++ty) {
					if (grid.find(hsh(tx, ty)) == grid.end()) continue;
					vector<int> &cur = grid[hsh(tx, ty)], tmp;
					for (int id : cur) {
						if (c->intersect(cir[id])) {
							ans[id] = c->i;
						} else {
							tmp.push_back(id);
						}
					}
					cur = move(tmp);
				}
			}
		}
	}

	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	256 KB	Output is correct
2	Correct	5 ms	256 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	4 ms	384 KB	Output is correct
7	Correct	4 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	4 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	5 ms	384 KB	Output is correct
17	Correct	5 ms	384 KB	Output is correct
18	Correct	6 ms	384 KB	Output is correct
19	Correct	8 ms	640 KB	Output is correct
20	Correct	8 ms	640 KB	Output is correct
21	Correct	8 ms	640 KB	Output is correct
22	Correct	18 ms	1024 KB	Output is correct
23	Correct	18 ms	1024 KB	Output is correct
24	Correct	18 ms	1024 KB	Output is correct
25	Correct	19 ms	896 KB	Output is correct
26	Correct	18 ms	1024 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	208 ms	13228 KB	Output is correct
2	Correct	223 ms	13516 KB	Output is correct
3	Correct	209 ms	15056 KB	Output is correct
4	Correct	195 ms	13256 KB	Output is correct
5	Correct	443 ms	15120 KB	Output is correct
6	Correct	936 ms	24224 KB	Output is correct
7	Correct	443 ms	16224 KB	Output is correct
8	Correct	519 ms	17888 KB	Output is correct

Subtask #3
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	417 ms	13092 KB	Output is correct
3	Correct	2007 ms	40084 KB	Output is correct
4	Correct	1944 ms	48204 KB	Output is correct
5	Correct	1512 ms	44076 KB	Output is correct
6	Correct	558 ms	22332 KB	Output is correct
7	Correct	220 ms	11804 KB	Output is correct
8	Correct	45 ms	2808 KB	Output is correct
9	Correct	1739 ms	47288 KB	Output is correct
10	Correct	1228 ms	42228 KB	Output is correct

Subtask #4
0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2160 ms	40120 KB	Output is correct
2	Execution timed out	3096 ms	45144 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #5
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	256 KB	Output is correct
2	Correct	5 ms	256 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	4 ms	384 KB	Output is correct
7	Correct	4 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	4 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	5 ms	384 KB	Output is correct
17	Correct	5 ms	384 KB	Output is correct
18	Correct	6 ms	384 KB	Output is correct
19	Correct	8 ms	640 KB	Output is correct
20	Correct	8 ms	640 KB	Output is correct
21	Correct	8 ms	640 KB	Output is correct
22	Correct	18 ms	1024 KB	Output is correct
23	Correct	18 ms	1024 KB	Output is correct
24	Correct	18 ms	1024 KB	Output is correct
25	Correct	19 ms	896 KB	Output is correct
26	Correct	18 ms	1024 KB	Output is correct
27	Correct	12 ms	896 KB	Output is correct
28	Correct	15 ms	896 KB	Output is correct
29	Correct	12 ms	896 KB	Output is correct
30	Correct	33 ms	1664 KB	Output is correct
31	Correct	34 ms	1656 KB	Output is correct
32	Correct	34 ms	1656 KB	Output is correct
33	Correct	78 ms	4588 KB	Output is correct
34	Correct	77 ms	4588 KB	Output is correct
35	Correct	79 ms	5200 KB	Output is correct
36	Correct	500 ms	13164 KB	Output is correct
37	Correct	501 ms	13164 KB	Output is correct
38	Correct	489 ms	13416 KB	Output is correct
39	Correct	305 ms	12068 KB	Output is correct
40	Correct	306 ms	12112 KB	Output is correct
41	Correct	303 ms	11964 KB	Output is correct
42	Correct	213 ms	10064 KB	Output is correct
43	Correct	498 ms	13004 KB	Output is correct
44	Correct	439 ms	12964 KB	Output is correct
45	Correct	447 ms	12988 KB	Output is correct
46	Correct	511 ms	13012 KB	Output is correct
47	Correct	528 ms	12936 KB	Output is correct
48	Correct	453 ms	12956 KB	Output is correct
49	Correct	436 ms	13016 KB	Output is correct
50	Correct	498 ms	13020 KB	Output is correct

Subtask #6
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	256 KB	Output is correct
2	Correct	5 ms	256 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	4 ms	384 KB	Output is correct
7	Correct	4 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	4 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	5 ms	384 KB	Output is correct
17	Correct	5 ms	384 KB	Output is correct
18	Correct	6 ms	384 KB	Output is correct
19	Correct	8 ms	640 KB	Output is correct
20	Correct	8 ms	640 KB	Output is correct
21	Correct	8 ms	640 KB	Output is correct
22	Correct	18 ms	1024 KB	Output is correct
23	Correct	18 ms	1024 KB	Output is correct
24	Correct	18 ms	1024 KB	Output is correct
25	Correct	19 ms	896 KB	Output is correct
26	Correct	18 ms	1024 KB	Output is correct
27	Correct	208 ms	13228 KB	Output is correct
28	Correct	223 ms	13516 KB	Output is correct
29	Correct	209 ms	15056 KB	Output is correct
30	Correct	195 ms	13256 KB	Output is correct
31	Correct	443 ms	15120 KB	Output is correct
32	Correct	936 ms	24224 KB	Output is correct
33	Correct	443 ms	16224 KB	Output is correct
34	Correct	519 ms	17888 KB	Output is correct
35	Correct	4 ms	384 KB	Output is correct
36	Correct	417 ms	13092 KB	Output is correct
37	Correct	2007 ms	40084 KB	Output is correct
38	Correct	1944 ms	48204 KB	Output is correct
39	Correct	1512 ms	44076 KB	Output is correct
40	Correct	558 ms	22332 KB	Output is correct
41	Correct	220 ms	11804 KB	Output is correct
42	Correct	45 ms	2808 KB	Output is correct
43	Correct	1739 ms	47288 KB	Output is correct
44	Correct	1228 ms	42228 KB	Output is correct
45	Correct	2160 ms	40120 KB	Output is correct
46	Execution timed out	3096 ms	45144 KB	Time limit exceeded
47	Halted	0 ms	0 KB	-

Submission #243432

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 12.0 / 12.0

Subtask #3 15.0 / 15.0

Subtask #4 0 / 23.0

Subtask #5 30.0 / 30.0

Subtask #6 0 / 13.0

Subtask #1
7.0 / 7.0

Subtask #2
12.0 / 12.0

Subtask #3
15.0 / 15.0

Subtask #4
0 / 23.0

Subtask #5
30.0 / 30.0

Subtask #6
0 / 13.0