oj.uz

Submission #502034

# Submission time Handle Problem Language Result Execution time Memory
502034 2022-01-05T06:20:23 Z CodeTiger927 Circle selection (APIO18_circle_selection) C++14
100 / 100
 1473 ms 54964 KB 
using namespace std;

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

#define MAXN 300005

typedef long long ll;
typedef pair<ll,ll> pll;

int N,vis[MAXN],ans[MAXN];
// current unit circle length
long long gl = 1e18;
vector<pair<pair<ll,int>,pll>> pts;
vector<ll> xs;
vector<vector<pair<ll,int>>> g;

int get(long long x) {
	x /= gl;
	return lower_bound(xs.begin(),xs.end(),x) - xs.begin();
}

long long sq(long long x) {
	return x * x;
}

bool check(int a,int b) {
	return sq(pts[a].second.first - pts[b].second.first) + sq(pts[a].second.second - pts[b].second.second) <= sq(pts[a].first.first + pts[b].first.first);
}

void reconstruct(long long nl) {
	// cout << "BEGIN RECONSTRUCTION!" << endl;
	gl = nl;
	g.clear();
	xs.clear();
	for(auto [a,b] : pts) {
		xs.push_back(b.first / gl);
	}
	sort(xs.begin(),xs.end());
	xs.resize(unique(xs.begin(),xs.end()) - xs.begin());
	g = vector<vector<pair<ll,int>>>(xs.size(),vector<pair<ll,int>>());
	for(int i = 0;i < N;++i) {
		if(!vis[i]) g[get(pts[i].second.first)].push_back({pts[i].second.second,i});
	}
	for(int i = 0;i < xs.size();++i) {
		sort(g[i].begin(),g[i].end());
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for(int i = 0;i < N;++i) {
		long long x,y,r;
		cin >> x >> y >> r;
		pts.push_back({{r,i},{x + 1e9,y + 1e9}});
	}
	sort(pts.begin(),pts.end(),[&](auto a,auto b) {return make_pair(-a.first.first,a.first.second) < make_pair(-b.first.first,b.first.second);});
	// reconstruct(1e18);
	for(int i = 0;i < N;++i) {
		if(vis[i]) continue;
		// cout << "TERMINATOR " << i << " " << (pts[i].first.second + 1) << endl;
		if(pts[i].first.first * 2 <= gl) {
			reconstruct(pts[i].first.first);
		}
		int x = get(pts[i].second.first);
		long long y = pts[i].second.second;
		long long r = pts[i].first.first;
		int index = pts[i].first.second;
		long long ly = (y / gl) * gl - 2 * gl;
		long long hy = (y / gl) * gl + 3 * gl;

		for(int j = max(0,x - 2);j <= min(x + 2,(int)xs.size() - 1);++j) {
			auto itr = lower_bound(g[j].begin(),g[j].end(),make_pair(ly,-1));
			for(;itr != g[j].end() && itr -> first <= hy;++itr) {
				if(check(i,itr -> second)) {
					// cout << (itr -> second) << endl;
					if(!vis[itr -> second]) vis[itr -> second] = index + 1;
				}
			}
		}
	}
	for(int i = 0;i < N;++i) {
		ans[pts[i].first.second] = vis[i];
	}
	for(int i = 0;i < N;++i) {
		cout << ans[i] << " \n"[i == N - 1];
	}
	return 0;
}

Compilation message

circle_selection.cpp: In function 'void reconstruct(long long int)':
circle_selection.cpp:37:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |  for(auto [a,b] : pts) {
      |           ^
circle_selection.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int i = 0;i < xs.size();++i) {
      |                ~~^~~~~~~~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:71:13: warning: unused variable 'r' [-Wunused-variable]
   71 |   long long r = pts[i].first.first;
      |             ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 3 ms 848 KB Output is correct
20 Correct 3 ms 848 KB Output is correct
21 Correct 4 ms 756 KB Output is correct
22 Correct 9 ms 1080 KB Output is correct
23 Correct 9 ms 976 KB Output is correct
24 Correct 9 ms 1104 KB Output is correct
25 Correct 8 ms 976 KB Output is correct
26 Correct 12 ms 1104 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 27296 KB Output is correct
2 Correct 181 ms 25432 KB Output is correct
3 Correct 173 ms 24856 KB Output is correct
4 Correct 205 ms 25904 KB Output is correct
5 Correct 325 ms 30356 KB Output is correct
6 Correct 517 ms 48624 KB Output is correct
7 Correct 440 ms 39728 KB Output is correct
8 Correct 439 ms 41508 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 251 ms 14288 KB Output is correct
3 Correct 844 ms 53728 KB Output is correct
4 Correct 837 ms 54152 KB Output is correct
5 Correct 777 ms 50964 KB Output is correct
6 Correct 235 ms 22900 KB Output is correct
7 Correct 142 ms 13328 KB Output is correct
8 Correct 25 ms 3264 KB Output is correct
9 Correct 827 ms 52376 KB Output is correct
10 Correct 480 ms 33120 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 26204 KB Output is correct
2 Correct 414 ms 39984 KB Output is correct
3 Correct 264 ms 31172 KB Output is correct
4 Correct 385 ms 39400 KB Output is correct
5 Correct 369 ms 40008 KB Output is correct
6 Correct 198 ms 29708 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 3 ms 848 KB Output is correct
20 Correct 3 ms 848 KB Output is correct
21 Correct 4 ms 756 KB Output is correct
22 Correct 9 ms 1080 KB Output is correct
23 Correct 9 ms 976 KB Output is correct
24 Correct 9 ms 1104 KB Output is correct
25 Correct 8 ms 976 KB Output is correct
26 Correct 12 ms 1104 KB Output is correct
27 Correct 9 ms 1088 KB Output is correct
28 Correct 8 ms 1164 KB Output is correct
29 Correct 8 ms 1100 KB Output is correct
30 Correct 22 ms 1700 KB Output is correct
31 Correct 24 ms 1880 KB Output is correct
32 Correct 19 ms 1868 KB Output is correct
33 Correct 60 ms 9196 KB Output is correct
34 Correct 59 ms 8624 KB Output is correct
35 Correct 119 ms 8516 KB Output is correct
36 Correct 271 ms 15520 KB Output is correct
37 Correct 246 ms 17972 KB Output is correct
38 Correct 242 ms 17092 KB Output is correct
39 Correct 386 ms 10744 KB Output is correct
40 Correct 320 ms 10788 KB Output is correct
41 Correct 329 ms 10744 KB Output is correct
42 Correct 61 ms 9984 KB Output is correct
43 Correct 94 ms 13500 KB Output is correct
44 Correct 100 ms 13616 KB Output is correct
45 Correct 92 ms 13540 KB Output is correct
46 Correct 95 ms 13616 KB Output is correct
47 Correct 103 ms 13488 KB Output is correct
48 Correct 101 ms 13488 KB Output is correct
49 Correct 109 ms 13504 KB Output is correct
50 Correct 114 ms 13488 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 3 ms 848 KB Output is correct
20 Correct 3 ms 848 KB Output is correct
21 Correct 4 ms 756 KB Output is correct
22 Correct 9 ms 1080 KB Output is correct
23 Correct 9 ms 976 KB Output is correct
24 Correct 9 ms 1104 KB Output is correct
25 Correct 8 ms 976 KB Output is correct
26 Correct 12 ms 1104 KB Output is correct
27 Correct 171 ms 27296 KB Output is correct
28 Correct 181 ms 25432 KB Output is correct
29 Correct 173 ms 24856 KB Output is correct
30 Correct 205 ms 25904 KB Output is correct
31 Correct 325 ms 30356 KB Output is correct
32 Correct 517 ms 48624 KB Output is correct
33 Correct 440 ms 39728 KB Output is correct
34 Correct 439 ms 41508 KB Output is correct
35 Correct 0 ms 204 KB Output is correct
36 Correct 251 ms 14288 KB Output is correct
37 Correct 844 ms 53728 KB Output is correct
38 Correct 837 ms 54152 KB Output is correct
39 Correct 777 ms 50964 KB Output is correct
40 Correct 235 ms 22900 KB Output is correct
41 Correct 142 ms 13328 KB Output is correct
42 Correct 25 ms 3264 KB Output is correct
43 Correct 827 ms 52376 KB Output is correct
44 Correct 480 ms 33120 KB Output is correct
45 Correct 345 ms 26204 KB Output is correct
46 Correct 414 ms 39984 KB Output is correct
47 Correct 264 ms 31172 KB Output is correct
48 Correct 385 ms 39400 KB Output is correct
49 Correct 369 ms 40008 KB Output is correct
50 Correct 198 ms 29708 KB Output is correct
51 Correct 9 ms 1088 KB Output is correct
52 Correct 8 ms 1164 KB Output is correct
53 Correct 8 ms 1100 KB Output is correct
54 Correct 22 ms 1700 KB Output is correct
55 Correct 24 ms 1880 KB Output is correct
56 Correct 19 ms 1868 KB Output is correct
57 Correct 60 ms 9196 KB Output is correct
58 Correct 59 ms 8624 KB Output is correct
59 Correct 119 ms 8516 KB Output is correct
60 Correct 271 ms 15520 KB Output is correct
61 Correct 246 ms 17972 KB Output is correct
62 Correct 242 ms 17092 KB Output is correct
63 Correct 386 ms 10744 KB Output is correct
64 Correct 320 ms 10788 KB Output is correct
65 Correct 329 ms 10744 KB Output is correct
66 Correct 61 ms 9984 KB Output is correct
67 Correct 94 ms 13500 KB Output is correct
68 Correct 100 ms 13616 KB Output is correct
69 Correct 92 ms 13540 KB Output is correct
70 Correct 95 ms 13616 KB Output is correct
71 Correct 103 ms 13488 KB Output is correct
72 Correct 101 ms 13488 KB Output is correct
73 Correct 109 ms 13504 KB Output is correct
74 Correct 114 ms 13488 KB Output is correct
75 Correct 386 ms 35268 KB Output is correct
76 Correct 229 ms 32792 KB Output is correct
77 Correct 205 ms 38256 KB Output is correct
78 Correct 194 ms 38020 KB Output is correct
79 Correct 464 ms 32592 KB Output is correct
80 Correct 200 ms 34488 KB Output is correct
81 Correct 765 ms 53860 KB Output is correct
82 Correct 799 ms 54092 KB Output is correct
83 Correct 787 ms 54156 KB Output is correct
84 Correct 755 ms 53048 KB Output is correct
85 Correct 787 ms 53780 KB Output is correct
86 Correct 882 ms 54484 KB Output is correct
87 Correct 693 ms 48000 KB Output is correct
88 Correct 1431 ms 34592 KB Output is correct
89 Correct 1461 ms 34572 KB Output is correct
90 Correct 1473 ms 34508 KB Output is correct
91 Correct 1302 ms 34528 KB Output is correct
92 Correct 1357 ms 34556 KB Output is correct
93 Correct 592 ms 46224 KB Output is correct
94 Correct 348 ms 33492 KB Output is correct
95 Correct 574 ms 46620 KB Output is correct
96 Correct 613 ms 46168 KB Output is correct
97 Correct 407 ms 30152 KB Output is correct
98 Correct 511 ms 54964 KB Output is correct
99 Correct 646 ms 46552 KB Output is correct
100 Correct 529 ms 46552 KB Output is correct
101 Correct 548 ms 52500 KB Output is correct
102 Correct 617 ms 46164 KB Output is correct
103 Correct 436 ms 32020 KB Output is correct
104 Correct 629 ms 46376 KB Output is correct
105 Correct 236 ms 29704 KB Output is correct
106 Correct 345 ms 38076 KB Output is correct
107 Correct 344 ms 38020 KB Output is correct
108 Correct 369 ms 38064 KB Output is correct
109 Correct 356 ms 37928 KB Output is correct
110 Correct 361 ms 37952 KB Output is correct
111 Correct 335 ms 38040 KB Output is correct
112 Correct 341 ms 38052 KB Output is correct
113 Correct 341 ms 37952 KB Output is correct
114 Correct 348 ms 37928 KB Output is correct
115 Correct 342 ms 38008 KB Output is correct
116 Correct 393 ms 39704 KB Output is correct