oj.uz

Submission #533452

# Submission time Handle Problem Language Result Execution time Memory
533452 2022-03-06T05:16:42 Z jjang36524 Circle selection (APIO18_circle_selection) C++14
64 / 100
 3000 ms 481160 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O0")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pi;
#define MAX 301010
#define MAXS 20
#define INF 1000000010
#define bb ' '
#define ln '\n'
#define Ln '\n'
pair<pll, pll> in[MAX];
ll X[MAX];
ll Y[MAX];
ll R[MAX];
ll ind[MAX];
int ri[MAX];
int ans[MAX];
inline ll sq(ll x) {
	return x * x;
}
inline bool chk(int i, int j) {
	return sq(X[i] - X[j]) + sq(Y[i] - Y[j]) <= sq(R[i] + R[j]);
}
bool isrange(int x, int y) {
	if (x < 0 || y < 0) return false;
	return true;
}
inline ll trans(int x, int y) {
	return ((ll)x * (ll)INF) + y;
}
bool cmp(pair<pll, pll>& p1, pair<pll, pll>& p2) {
	if (p1.first.first == p2.first.first) return p1.first.second < p2.first.second;
	else return p1.first.first > p2.first.first;
}
unordered_map<ll, vector<int>> mp;
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N;
	cin >> N;
	int i;
	for (i = 1; i <= N; i++) cin >> in[i].second.first >> in[i].second.second >> in[i].first.first, in[i].first.second = i;
	sort(in + 1, in + N + 1, cmp);
	for (i = 1; i <= N; i++) tie(X[i], Y[i], R[i], ind[i]) = make_tuple(in[i].second.first + INF, in[i].second.second + INF, in[i].first.first, in[i].first.second);
	int k;
	int s, e;
	e = 0;
	for (k = 30; k >= 0; k--) {
		int r = 1 << k;
		s = e + 1;
		if (R[s] < r / 2) continue;
		mp.clear();
		e = 0;
		for (i = s; i <= N; i++) {
			if (ans[i]) continue;
			int x, y;
			x = X[i] >> k;
			y = Y[i] >> k;
			if (R[i] < r / 2 && !e) e = i - 1;
			int xx, yy;
			mp[((ll)x << 31LL) + y].push_back(i);
		}
		if (e == 0) e = N;
		for (i = s; i <= e; i++) {
			if (ans[i]) continue;
			ans[i] = i;
			int x, y;
			x = X[i] / r;
			y = Y[i] / r;
			int xx, yy;
			for (xx = x - 2; xx <= x + 2; xx++) for (yy = y - 2; yy <= y + 2; yy++) {
				ll t = ((ll)xx << 31LL) + yy;
				vector<int> v;
				if (abs(x - xx) + abs(y - yy) <= 2) {
					for (auto c : mp[t]) {
						if (!ans[c] && chk(c, i)) ans[c] = i;
						if (!ans[c]) v.push_back(c);
					}
					mp[t] = v;
				}
				else {
					for (auto c : mp[t]) if (!ans[c] && chk(c, i)) ans[c] = i;
				}
			}
		}
	}
	for (i = 1; i <= N; i++) ri[ind[i]] = i;
	for (i = 1; i <= N; i++) cout << ind[ans[ri[i]]] << bb;
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:64:8: warning: unused variable 'xx' [-Wunused-variable]
   64 |    int xx, yy;
      |        ^~
circle_selection.cpp:64:12: warning: unused variable 'yy' [-Wunused-variable]
   64 |    int xx, yy;
      |            ^~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 1 ms 460 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 716 KB Output is correct
20 Correct 3 ms 716 KB Output is correct
21 Correct 3 ms 716 KB Output is correct
22 Correct 18 ms 4060 KB Output is correct
23 Correct 19 ms 4248 KB Output is correct
24 Correct 18 ms 3752 KB Output is correct
25 Correct 17 ms 3992 KB Output is correct
26 Correct 18 ms 4120 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 24528 KB Output is correct
2 Correct 149 ms 24284 KB Output is correct
3 Correct 143 ms 24060 KB Output is correct
4 Correct 150 ms 23876 KB Output is correct
5 Correct 169 ms 26740 KB Output is correct
6 Correct 921 ms 61460 KB Output is correct
7 Correct 212 ms 28548 KB Output is correct
8 Correct 295 ms 35360 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 833 ms 70916 KB Output is correct
3 Correct 2660 ms 187292 KB Output is correct
4 Correct 2690 ms 180708 KB Output is correct
5 Correct 2182 ms 152876 KB Output is correct
6 Correct 796 ms 72024 KB Output is correct
7 Correct 398 ms 58276 KB Output is correct
8 Correct 41 ms 9532 KB Output is correct
9 Correct 2730 ms 173020 KB Output is correct
10 Correct 1668 ms 145516 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2968 ms 479612 KB Output is correct
2 Execution timed out 3020 ms 481160 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 1 ms 460 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 716 KB Output is correct
20 Correct 3 ms 716 KB Output is correct
21 Correct 3 ms 716 KB Output is correct
22 Correct 18 ms 4060 KB Output is correct
23 Correct 19 ms 4248 KB Output is correct
24 Correct 18 ms 3752 KB Output is correct
25 Correct 17 ms 3992 KB Output is correct
26 Correct 18 ms 4120 KB Output is correct
27 Correct 7 ms 1316 KB Output is correct
28 Correct 6 ms 1292 KB Output is correct
29 Correct 6 ms 1348 KB Output is correct
30 Correct 39 ms 8776 KB Output is correct
31 Correct 41 ms 8768 KB Output is correct
32 Correct 40 ms 7516 KB Output is correct
33 Correct 53 ms 8244 KB Output is correct
34 Correct 55 ms 8348 KB Output is correct
35 Correct 54 ms 8308 KB Output is correct
36 Correct 806 ms 76120 KB Output is correct
37 Correct 871 ms 69036 KB Output is correct
38 Correct 817 ms 76628 KB Output is correct
39 Correct 235 ms 14312 KB Output is correct
40 Correct 249 ms 14224 KB Output is correct
41 Correct 219 ms 14256 KB Output is correct
42 Correct 104 ms 13428 KB Output is correct
43 Correct 780 ms 136104 KB Output is correct
44 Correct 931 ms 136360 KB Output is correct
45 Correct 757 ms 136184 KB Output is correct
46 Correct 874 ms 136284 KB Output is correct
47 Correct 752 ms 136416 KB Output is correct
48 Correct 771 ms 136284 KB Output is correct
49 Correct 777 ms 136420 KB Output is correct
50 Correct 760 ms 136168 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 1 ms 460 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 716 KB Output is correct
20 Correct 3 ms 716 KB Output is correct
21 Correct 3 ms 716 KB Output is correct
22 Correct 18 ms 4060 KB Output is correct
23 Correct 19 ms 4248 KB Output is correct
24 Correct 18 ms 3752 KB Output is correct
25 Correct 17 ms 3992 KB Output is correct
26 Correct 18 ms 4120 KB Output is correct
27 Correct 156 ms 24528 KB Output is correct
28 Correct 149 ms 24284 KB Output is correct
29 Correct 143 ms 24060 KB Output is correct
30 Correct 150 ms 23876 KB Output is correct
31 Correct 169 ms 26740 KB Output is correct
32 Correct 921 ms 61460 KB Output is correct
33 Correct 212 ms 28548 KB Output is correct
34 Correct 295 ms 35360 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 833 ms 70916 KB Output is correct
37 Correct 2660 ms 187292 KB Output is correct
38 Correct 2690 ms 180708 KB Output is correct
39 Correct 2182 ms 152876 KB Output is correct
40 Correct 796 ms 72024 KB Output is correct
41 Correct 398 ms 58276 KB Output is correct
42 Correct 41 ms 9532 KB Output is correct
43 Correct 2730 ms 173020 KB Output is correct
44 Correct 1668 ms 145516 KB Output is correct
45 Correct 2968 ms 479612 KB Output is correct
46 Execution timed out 3020 ms 481160 KB Time limit exceeded
47 Halted 0 ms 0 KB -