oj.uz

Submission #373454

# Submission time Handle Problem Language Result Execution time Memory
373454 2021-03-04T16:39:23 Z LucaDantas Circle selection (APIO18_circle_selection) C++17
100 / 100
 673 ms 45440 KB 
#include<bits/stdc++.h>
using namespace std;

#define pb push_back

constexpr int maxn = 3e5+10, shift = 1000000011;

struct Circle
{
	int x, y, r, id;
	void db() {
		printf("(%d %d %d) ", x, y, r);
	}
} cc[maxn];

long long sq(int x) { return 1ll * x * x; }
bool intersect(Circle a, Circle b) {
	return sq(a.x - b.x) + sq(a.y - b.y) <= sq(a.r + b.r);
}

int B, n, ans[maxn];

vector<vector<Circle>> blocks;

void setBlocks() {
	sort(cc, cc+n, [](Circle a, Circle b) {
		if((a.x>>B) != (b.x>>B)) return a.x < b.x;
		return a.y < b.y;
	});
	vector<Circle> here = {cc[0]};
	for(int i = 1, last = cc[0].x; i < n; i++) {
		if((last>>B) == (cc[i].x>>B)) here.pb(cc[i]);
		else blocks.pb(here), here = {cc[i]};
		last = cc[i].x;
	}
	blocks.pb(here);
}

void doit(int i, int c) {
	int L = 0, R = (int)blocks[i].size()-1, best = -1, index = (cc[c].y>>B);
	while(L <= R) {
		int m = (L+R) >> 1;
		if((blocks[i][m].y>>B) >= index-2) best = m, R = m-1;
		else L = m+1;
	}
	if(best == -1) return;
	for(; best < (int)blocks[i].size() && (blocks[i][best].y>>B) <= index+2; ++best) {
		if(intersect(cc[c], blocks[i][best]) && !ans[blocks[i][best].id])
			ans[blocks[i][best].id] = cc[c].id+1;
	}
}

void rescale() {
	vector<vector<Circle>> aux;
	for(vector<Circle> BLOCO : blocks) {
		int index1 = ~(1<<31);
		for(Circle c : BLOCO)
			if(!ans[c.id])
				index1 = min(index1, (c.x>>B));
		if(index1 == (~(1<<31))) continue;
		vector<Circle> grp[2];
		for(Circle c : BLOCO)
			if(!ans[c.id])
				grp[(c.x>>B) != index1].pb(c);
		for(int b : {0, 1})
			if(grp[b].size()) aux.pb(grp[b]);
	}
	blocks = aux;
}

int main() {
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
		scanf("%d %d %d", &cc[i].x, &cc[i].y, &cc[i].r);
		cc[i].x += shift; cc[i].y += shift;
		cc[i].id = i; B = max(B, cc[i].r);
	}
	B = 32 - __builtin_clz(B-1);
	setBlocks();

	sort(cc, cc+n, [](Circle a, Circle b) {
		if(a.r == b.r) return a.id < b.id;
		return a.r > b.r;
	});
	for(int i = 0; i < n; i++) {
		if(ans[cc[i].id]) continue;
		auto [x, y, r, id] = cc[i];
		while((1 << B) >= (r << 1))
			--B, rescale();

		int L = 0, R = (int)blocks.size()-1, best = -1, index = (x>>B);
		while(L <= R) {
			int m = (L+R) >> 1;
			if((blocks[m][0].x>>B) >= index-2) best = m, R = m-1;
			else L = m+1;
		}

		while(best < (int)blocks.size() && (blocks[best][0].x>>B) <= index+2)
			doit(best, i), ++best;
	}

	for(int i = 0; i < n; i++)
		printf("%d ", ans[i]);
	puts("");
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
circle_selection.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |   scanf("%d %d %d", &cc[i].x, &cc[i].y, &cc[i].r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 20536 KB Output is correct
2 Correct 202 ms 17356 KB Output is correct
3 Correct 197 ms 15292 KB Output is correct
4 Correct 216 ms 18316 KB Output is correct
5 Correct 211 ms 15924 KB Output is correct
6 Correct 304 ms 24092 KB Output is correct
7 Correct 232 ms 16840 KB Output is correct
8 Correct 231 ms 17696 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 130 ms 9528 KB Output is correct
3 Correct 453 ms 24432 KB Output is correct
4 Correct 437 ms 24816 KB Output is correct
5 Correct 392 ms 25384 KB Output is correct
6 Correct 174 ms 14904 KB Output is correct
7 Correct 88 ms 8124 KB Output is correct
8 Correct 17 ms 2044 KB Output is correct
9 Correct 438 ms 23740 KB Output is correct
10 Correct 361 ms 25068 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 18208 KB Output is correct
2 Correct 515 ms 45440 KB Output is correct
3 Correct 254 ms 15084 KB Output is correct
4 Correct 468 ms 28696 KB Output is correct
5 Correct 457 ms 28312 KB Output is correct
6 Correct 241 ms 14872 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 380 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 4 ms 748 KB Output is correct
20 Correct 4 ms 748 KB Output is correct
21 Correct 4 ms 796 KB Output is correct
22 Correct 6 ms 1000 KB Output is correct
23 Correct 6 ms 876 KB Output is correct
24 Correct 6 ms 1004 KB Output is correct
25 Correct 6 ms 1004 KB Output is correct
26 Correct 7 ms 1004 KB Output is correct
27 Correct 8 ms 1152 KB Output is correct
28 Correct 7 ms 1024 KB Output is correct
29 Correct 8 ms 1004 KB Output is correct
30 Correct 12 ms 1388 KB Output is correct
31 Correct 13 ms 1900 KB Output is correct
32 Correct 12 ms 1520 KB Output is correct
33 Correct 74 ms 6876 KB Output is correct
34 Correct 79 ms 7260 KB Output is correct
35 Correct 76 ms 6924 KB Output is correct
36 Correct 142 ms 13088 KB Output is correct
37 Correct 139 ms 12320 KB Output is correct
38 Correct 136 ms 12080 KB Output is correct
39 Correct 196 ms 13468 KB Output is correct
40 Correct 194 ms 13576 KB Output is correct
41 Correct 201 ms 13508 KB Output is correct
42 Correct 82 ms 5996 KB Output is correct
43 Correct 110 ms 10908 KB Output is correct
44 Correct 115 ms 10908 KB Output is correct
45 Correct 110 ms 10908 KB Output is correct
46 Correct 110 ms 10908 KB Output is correct
47 Correct 112 ms 10908 KB Output is correct
48 Correct 110 ms 10908 KB Output is correct
49 Correct 110 ms 10908 KB Output is correct
50 Correct 111 ms 10908 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 380 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 4 ms 748 KB Output is correct
20 Correct 4 ms 748 KB Output is correct
21 Correct 4 ms 796 KB Output is correct
22 Correct 6 ms 1000 KB Output is correct
23 Correct 6 ms 876 KB Output is correct
24 Correct 6 ms 1004 KB Output is correct
25 Correct 6 ms 1004 KB Output is correct
26 Correct 7 ms 1004 KB Output is correct
27 Correct 200 ms 20536 KB Output is correct
28 Correct 202 ms 17356 KB Output is correct
29 Correct 197 ms 15292 KB Output is correct
30 Correct 216 ms 18316 KB Output is correct
31 Correct 211 ms 15924 KB Output is correct
32 Correct 304 ms 24092 KB Output is correct
33 Correct 232 ms 16840 KB Output is correct
34 Correct 231 ms 17696 KB Output is correct
35 Correct 1 ms 364 KB Output is correct
36 Correct 130 ms 9528 KB Output is correct
37 Correct 453 ms 24432 KB Output is correct
38 Correct 437 ms 24816 KB Output is correct
39 Correct 392 ms 25384 KB Output is correct
40 Correct 174 ms 14904 KB Output is correct
41 Correct 88 ms 8124 KB Output is correct
42 Correct 17 ms 2044 KB Output is correct
43 Correct 438 ms 23740 KB Output is correct
44 Correct 361 ms 25068 KB Output is correct
45 Correct 396 ms 18208 KB Output is correct
46 Correct 515 ms 45440 KB Output is correct
47 Correct 254 ms 15084 KB Output is correct
48 Correct 468 ms 28696 KB Output is correct
49 Correct 457 ms 28312 KB Output is correct
50 Correct 241 ms 14872 KB Output is correct
51 Correct 8 ms 1152 KB Output is correct
52 Correct 7 ms 1024 KB Output is correct
53 Correct 8 ms 1004 KB Output is correct
54 Correct 12 ms 1388 KB Output is correct
55 Correct 13 ms 1900 KB Output is correct
56 Correct 12 ms 1520 KB Output is correct
57 Correct 74 ms 6876 KB Output is correct
58 Correct 79 ms 7260 KB Output is correct
59 Correct 76 ms 6924 KB Output is correct
60 Correct 142 ms 13088 KB Output is correct
61 Correct 139 ms 12320 KB Output is correct
62 Correct 136 ms 12080 KB Output is correct
63 Correct 196 ms 13468 KB Output is correct
64 Correct 194 ms 13576 KB Output is correct
65 Correct 201 ms 13508 KB Output is correct
66 Correct 82 ms 5996 KB Output is correct
67 Correct 110 ms 10908 KB Output is correct
68 Correct 115 ms 10908 KB Output is correct
69 Correct 110 ms 10908 KB Output is correct
70 Correct 110 ms 10908 KB Output is correct
71 Correct 112 ms 10908 KB Output is correct
72 Correct 110 ms 10908 KB Output is correct
73 Correct 110 ms 10908 KB Output is correct
74 Correct 111 ms 10908 KB Output is correct
75 Correct 241 ms 23296 KB Output is correct
76 Correct 233 ms 21488 KB Output is correct
77 Correct 232 ms 21988 KB Output is correct
78 Correct 226 ms 23252 KB Output is correct
79 Correct 247 ms 21252 KB Output is correct
80 Correct 225 ms 23380 KB Output is correct
81 Correct 459 ms 33080 KB Output is correct
82 Correct 488 ms 31544 KB Output is correct
83 Correct 479 ms 32072 KB Output is correct
84 Correct 436 ms 28348 KB Output is correct
85 Correct 455 ms 31460 KB Output is correct
86 Correct 472 ms 32756 KB Output is correct
87 Correct 433 ms 25452 KB Output is correct
88 Correct 655 ms 40748 KB Output is correct
89 Correct 650 ms 40656 KB Output is correct
90 Correct 659 ms 41020 KB Output is correct
91 Correct 641 ms 40860 KB Output is correct
92 Correct 673 ms 40844 KB Output is correct
93 Correct 491 ms 43768 KB Output is correct
94 Correct 346 ms 28776 KB Output is correct
95 Correct 518 ms 45312 KB Output is correct
96 Correct 477 ms 41984 KB Output is correct
97 Correct 455 ms 23680 KB Output is correct
98 Correct 343 ms 29088 KB Output is correct
99 Correct 490 ms 43520 KB Output is correct
100 Correct 456 ms 42112 KB Output is correct
101 Correct 369 ms 27468 KB Output is correct
102 Correct 478 ms 42496 KB Output is correct
103 Correct 519 ms 28580 KB Output is correct
104 Correct 480 ms 42496 KB Output is correct
105 Correct 286 ms 17708 KB Output is correct
106 Correct 393 ms 29616 KB Output is correct
107 Correct 401 ms 29712 KB Output is correct
108 Correct 395 ms 29712 KB Output is correct
109 Correct 402 ms 29584 KB Output is correct
110 Correct 395 ms 29584 KB Output is correct
111 Correct 398 ms 29712 KB Output is correct
112 Correct 394 ms 29872 KB Output is correct
113 Correct 394 ms 29584 KB Output is correct
114 Correct 397 ms 29712 KB Output is correct
115 Correct 415 ms 29724 KB Output is correct
116 Correct 400 ms 33688 KB Output is correct