답안 #243436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
243436	2020-07-01T06:52:47 Z	atoiz	원 고르기 (APIO18_circle_selection)	C++14	100 / 100	1211 ms	41484 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()*/100);
 
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<int_fast64_t, vector<int>> grid;
 
inline int_fast64_t hsh(int x, int y) { return (((int_fast64_t) 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) {
		if (c != vec.end() && c->r > ((1 << i) >> 1)) {
			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 << ' ';
	cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	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	Correct	5 ms	384 KB	Output is correct
5	Correct	5 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	Correct	4 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	256 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	5 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	13 ms	1024 KB	Output is correct
23	Correct	13 ms	1024 KB	Output is correct
24	Correct	13 ms	1024 KB	Output is correct
25	Correct	12 ms	1024 KB	Output is correct
26	Correct	14 ms	1024 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	198 ms	13868 KB	Output is correct
2	Correct	197 ms	13208 KB	Output is correct
3	Correct	194 ms	13384 KB	Output is correct
4	Correct	198 ms	13264 KB	Output is correct
5	Correct	210 ms	13236 KB	Output is correct
6	Correct	609 ms	23868 KB	Output is correct
7	Correct	243 ms	17016 KB	Output is correct
8	Correct	294 ms	18984 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	289 ms	13092 KB	Output is correct
3	Correct	1105 ms	40844 KB	Output is correct
4	Correct	1157 ms	40844 KB	Output is correct
5	Correct	1174 ms	37004 KB	Output is correct
6	Correct	398 ms	19004 KB	Output is correct
7	Correct	150 ms	10632 KB	Output is correct
8	Correct	25 ms	2808 KB	Output is correct
9	Correct	1127 ms	40072 KB	Output is correct
10	Correct	1020 ms	34700 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1016 ms	39948 KB	Output is correct
2	Correct	969 ms	41056 KB	Output is correct
3	Correct	364 ms	20616 KB	Output is correct
4	Correct	900 ms	41100 KB	Output is correct
5	Correct	898 ms	41228 KB	Output is correct
6	Correct	232 ms	16508 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	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	Correct	5 ms	384 KB	Output is correct
5	Correct	5 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	Correct	4 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	256 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	5 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	13 ms	1024 KB	Output is correct
23	Correct	13 ms	1024 KB	Output is correct
24	Correct	13 ms	1024 KB	Output is correct
25	Correct	12 ms	1024 KB	Output is correct
26	Correct	14 ms	1024 KB	Output is correct
27	Correct	11 ms	896 KB	Output is correct
28	Correct	11 ms	948 KB	Output is correct
29	Correct	11 ms	896 KB	Output is correct
30	Correct	21 ms	1664 KB	Output is correct
31	Correct	21 ms	1664 KB	Output is correct
32	Correct	21 ms	1664 KB	Output is correct
33	Correct	72 ms	4716 KB	Output is correct
34	Correct	72 ms	4588 KB	Output is correct
35	Correct	71 ms	4832 KB	Output is correct
36	Correct	305 ms	13192 KB	Output is correct
37	Correct	284 ms	14216 KB	Output is correct
38	Correct	352 ms	14216 KB	Output is correct
39	Correct	246 ms	13032 KB	Output is correct
40	Correct	252 ms	13060 KB	Output is correct
41	Correct	260 ms	13220 KB	Output is correct
42	Correct	151 ms	11148 KB	Output is correct
43	Correct	237 ms	14088 KB	Output is correct
44	Correct	234 ms	14088 KB	Output is correct
45	Correct	239 ms	14056 KB	Output is correct
46	Correct	267 ms	14088 KB	Output is correct
47	Correct	293 ms	14088 KB	Output is correct
48	Correct	248 ms	14088 KB	Output is correct
49	Correct	239 ms	14040 KB	Output is correct
50	Correct	229 ms	14088 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	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	Correct	5 ms	384 KB	Output is correct
5	Correct	5 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	Correct	4 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	256 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	5 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	13 ms	1024 KB	Output is correct
23	Correct	13 ms	1024 KB	Output is correct
24	Correct	13 ms	1024 KB	Output is correct
25	Correct	12 ms	1024 KB	Output is correct
26	Correct	14 ms	1024 KB	Output is correct
27	Correct	198 ms	13868 KB	Output is correct
28	Correct	197 ms	13208 KB	Output is correct
29	Correct	194 ms	13384 KB	Output is correct
30	Correct	198 ms	13264 KB	Output is correct
31	Correct	210 ms	13236 KB	Output is correct
32	Correct	609 ms	23868 KB	Output is correct
33	Correct	243 ms	17016 KB	Output is correct
34	Correct	294 ms	18984 KB	Output is correct
35	Correct	5 ms	384 KB	Output is correct
36	Correct	289 ms	13092 KB	Output is correct
37	Correct	1105 ms	40844 KB	Output is correct
38	Correct	1157 ms	40844 KB	Output is correct
39	Correct	1174 ms	37004 KB	Output is correct
40	Correct	398 ms	19004 KB	Output is correct
41	Correct	150 ms	10632 KB	Output is correct
42	Correct	25 ms	2808 KB	Output is correct
43	Correct	1127 ms	40072 KB	Output is correct
44	Correct	1020 ms	34700 KB	Output is correct
45	Correct	1016 ms	39948 KB	Output is correct
46	Correct	969 ms	41056 KB	Output is correct
47	Correct	364 ms	20616 KB	Output is correct
48	Correct	900 ms	41100 KB	Output is correct
49	Correct	898 ms	41228 KB	Output is correct
50	Correct	232 ms	16508 KB	Output is correct
51	Correct	11 ms	896 KB	Output is correct
52	Correct	11 ms	948 KB	Output is correct
53	Correct	11 ms	896 KB	Output is correct
54	Correct	21 ms	1664 KB	Output is correct
55	Correct	21 ms	1664 KB	Output is correct
56	Correct	21 ms	1664 KB	Output is correct
57	Correct	72 ms	4716 KB	Output is correct
58	Correct	72 ms	4588 KB	Output is correct
59	Correct	71 ms	4832 KB	Output is correct
60	Correct	305 ms	13192 KB	Output is correct
61	Correct	284 ms	14216 KB	Output is correct
62	Correct	352 ms	14216 KB	Output is correct
63	Correct	246 ms	13032 KB	Output is correct
64	Correct	252 ms	13060 KB	Output is correct
65	Correct	260 ms	13220 KB	Output is correct
66	Correct	151 ms	11148 KB	Output is correct
67	Correct	237 ms	14088 KB	Output is correct
68	Correct	234 ms	14088 KB	Output is correct
69	Correct	239 ms	14056 KB	Output is correct
70	Correct	267 ms	14088 KB	Output is correct
71	Correct	293 ms	14088 KB	Output is correct
72	Correct	248 ms	14088 KB	Output is correct
73	Correct	239 ms	14040 KB	Output is correct
74	Correct	229 ms	14088 KB	Output is correct
75	Correct	223 ms	14780 KB	Output is correct
76	Correct	221 ms	14740 KB	Output is correct
77	Correct	223 ms	14900 KB	Output is correct
78	Correct	211 ms	14480 KB	Output is correct
79	Correct	241 ms	14316 KB	Output is correct
80	Correct	221 ms	14336 KB	Output is correct
81	Correct	1211 ms	41096 KB	Output is correct
82	Correct	1016 ms	41108 KB	Output is correct
83	Correct	1012 ms	41148 KB	Output is correct
84	Correct	985 ms	40968 KB	Output is correct
85	Correct	1032 ms	41100 KB	Output is correct
86	Correct	1166 ms	41100 KB	Output is correct
87	Correct	999 ms	40712 KB	Output is correct
88	Correct	887 ms	37524 KB	Output is correct
89	Correct	888 ms	37660 KB	Output is correct
90	Correct	893 ms	37604 KB	Output is correct
91	Correct	882 ms	37504 KB	Output is correct
92	Correct	934 ms	37448 KB	Output is correct
93	Correct	1026 ms	40968 KB	Output is correct
94	Correct	929 ms	40712 KB	Output is correct
95	Correct	1104 ms	40752 KB	Output is correct
96	Correct	990 ms	41364 KB	Output is correct
97	Correct	990 ms	41484 KB	Output is correct
98	Correct	726 ms	27684 KB	Output is correct
99	Correct	1073 ms	41352 KB	Output is correct
100	Correct	1028 ms	41352 KB	Output is correct
101	Correct	1061 ms	31292 KB	Output is correct
102	Correct	925 ms	40716 KB	Output is correct
103	Correct	1100 ms	40532 KB	Output is correct
104	Correct	1014 ms	41352 KB	Output is correct
105	Correct	765 ms	30084 KB	Output is correct
106	Correct	905 ms	39564 KB	Output is correct
107	Correct	773 ms	39820 KB	Output is correct
108	Correct	906 ms	39560 KB	Output is correct
109	Correct	761 ms	39476 KB	Output is correct
110	Correct	869 ms	39436 KB	Output is correct
111	Correct	822 ms	39608 KB	Output is correct
112	Correct	852 ms	39436 KB	Output is correct
113	Correct	846 ms	39444 KB	Output is correct
114	Correct	799 ms	39304 KB	Output is correct
115	Correct	957 ms	39476 KB	Output is correct
116	Correct	818 ms	39504 KB	Output is correct

답안 #243436

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 12.0 / 12.0

Subtask #3 15.0 / 15.0

Subtask #4 23.0 / 23.0

Subtask #5 30.0 / 30.0

Subtask #6 13.0 / 13.0

Subtask #1
7.0 / 7.0

Subtask #2
12.0 / 12.0

Subtask #3
15.0 / 15.0

Subtask #4
23.0 / 23.0

Subtask #5
30.0 / 30.0

Subtask #6
13.0 / 13.0