oj.uz

Submission #579080

# Submission time Handle Problem Language Result Execution time Memory
579080 2022-06-18T11:15:30 Z noedit Circle selection (APIO18_circle_selection) C++17
72 / 100
 3000 ms 255968 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<pi, pi> in[MAX];
int X[MAX];
int Y[MAX];
int R[MAX];
int 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<pi, pi>& p1, pair<pi, pi>& 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;
			for (xx = x - 1; xx <= x + 1; xx++) for (yy = y - 1; yy <= y + 1; yy++) {
				mp[((ll)xx << 31LL) + yy].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] >>k;
			y = Y[i] >>k;
			int xx, yy;
			for (xx = x - 1; xx <= x + 1; xx++) for (yy = y - 1; yy <= y + 1; yy++) {
				ll t = ((ll)xx << 31LL) + yy;
				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;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 328 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 472 KB Output is correct
18 Correct 1 ms 504 KB Output is correct
19 Correct 5 ms 980 KB Output is correct
20 Correct 4 ms 980 KB Output is correct
21 Correct 4 ms 980 KB Output is correct
22 Correct 17 ms 4912 KB Output is correct
23 Correct 21 ms 4912 KB Output is correct
24 Correct 18 ms 4900 KB Output is correct
25 Correct 23 ms 4900 KB Output is correct
26 Correct 21 ms 4948 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 22128 KB Output is correct
2 Correct 208 ms 22992 KB Output is correct
3 Correct 198 ms 23120 KB Output is correct
4 Correct 209 ms 22592 KB Output is correct
5 Correct 300 ms 34520 KB Output is correct
6 Correct 1477 ms 65848 KB Output is correct
7 Correct 397 ms 37020 KB Output is correct
8 Correct 598 ms 44684 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 942 ms 85220 KB Output is correct
3 Correct 2719 ms 247964 KB Output is correct
4 Correct 2766 ms 255508 KB Output is correct
5 Execution timed out 3105 ms 171100 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1357 ms 248280 KB Output is correct
2 Correct 1377 ms 255732 KB Output is correct
3 Correct 488 ms 45656 KB Output is correct
4 Correct 1462 ms 255856 KB Output is correct
5 Correct 1553 ms 255968 KB Output is correct
6 Correct 314 ms 40460 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 328 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 472 KB Output is correct
18 Correct 1 ms 504 KB Output is correct
19 Correct 5 ms 980 KB Output is correct
20 Correct 4 ms 980 KB Output is correct
21 Correct 4 ms 980 KB Output is correct
22 Correct 17 ms 4912 KB Output is correct
23 Correct 21 ms 4912 KB Output is correct
24 Correct 18 ms 4900 KB Output is correct
25 Correct 23 ms 4900 KB Output is correct
26 Correct 21 ms 4948 KB Output is correct
27 Correct 8 ms 1520 KB Output is correct
28 Correct 9 ms 1492 KB Output is correct
29 Correct 8 ms 1464 KB Output is correct
30 Correct 62 ms 9512 KB Output is correct
31 Correct 85 ms 9596 KB Output is correct
32 Correct 63 ms 9592 KB Output is correct
33 Correct 91 ms 8400 KB Output is correct
34 Correct 87 ms 8440 KB Output is correct
35 Correct 85 ms 8740 KB Output is correct
36 Correct 1164 ms 87308 KB Output is correct
37 Correct 1046 ms 87380 KB Output is correct
38 Correct 1091 ms 87260 KB Output is correct
39 Correct 787 ms 18716 KB Output is correct
40 Correct 723 ms 18480 KB Output is correct
41 Correct 702 ms 18588 KB Output is correct
42 Correct 212 ms 16104 KB Output is correct
43 Correct 484 ms 82488 KB Output is correct
44 Correct 678 ms 82172 KB Output is correct
45 Correct 487 ms 81916 KB Output is correct
46 Correct 501 ms 82152 KB Output is correct
47 Correct 480 ms 82020 KB Output is correct
48 Correct 490 ms 82008 KB Output is correct
49 Correct 474 ms 82148 KB Output is correct
50 Correct 459 ms 82024 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 328 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 472 KB Output is correct
18 Correct 1 ms 504 KB Output is correct
19 Correct 5 ms 980 KB Output is correct
20 Correct 4 ms 980 KB Output is correct
21 Correct 4 ms 980 KB Output is correct
22 Correct 17 ms 4912 KB Output is correct
23 Correct 21 ms 4912 KB Output is correct
24 Correct 18 ms 4900 KB Output is correct
25 Correct 23 ms 4900 KB Output is correct
26 Correct 21 ms 4948 KB Output is correct
27 Correct 197 ms 22128 KB Output is correct
28 Correct 208 ms 22992 KB Output is correct
29 Correct 198 ms 23120 KB Output is correct
30 Correct 209 ms 22592 KB Output is correct
31 Correct 300 ms 34520 KB Output is correct
32 Correct 1477 ms 65848 KB Output is correct
33 Correct 397 ms 37020 KB Output is correct
34 Correct 598 ms 44684 KB Output is correct
35 Correct 0 ms 340 KB Output is correct
36 Correct 942 ms 85220 KB Output is correct
37 Correct 2719 ms 247964 KB Output is correct
38 Correct 2766 ms 255508 KB Output is correct
39 Execution timed out 3105 ms 171100 KB Time limit exceeded
40 Halted 0 ms 0 KB -