oj.uz

Submission #533395

# Submission time Handle Problem Language Result Execution time Memory
533395 2022-03-05T21:07:44 Z flappybird Circle selection (APIO18_circle_selection) C++14
49 / 100
 3000 ms 456852 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O0")
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];
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;
}
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) continue;
		unordered_map<ll, vector<int>> mp;
		e = 0;
		for (i = s; i <= N; i++) {
			if (ans[i]) continue;
			int x, y;
			x = X[i] / r;
			y = Y[i] / r;
			if (R[i] < r && !e) e = i - 1;
			int xx, yy;
			if (R[i] <= r) {
				for (xx = x - 1; xx <= x + 1; xx++) for (yy = y - 1; yy <= y + 1; yy++) mp[((ll)xx * (ll)INF) + yy].push_back(i);
			}
			else {
				for (xx = x - 2; xx <= x + 2; xx++) for (yy = y - 2; yy <= y + 2; yy++) if (!(max(abs(x - xx), abs(y - yy)) & 1)) mp[((ll)xx * (ll)INF) + 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] / r;
			y = Y[i] / r;
			int xx, yy;
			if (R[i] <= r) {
				for (xx = x - 1; xx <= x + 1; xx++) for (yy = y - 1; yy <= y + 1; yy++) {
					ll t = ((ll)xx * (ll)INF) + yy;
					for (auto c : mp[t]) if (!ans[c] && chk(c, i)) ans[c] = i;
				}
			}
			else {
				for (xx = x - 2; xx <= x + 2; xx++) for (yy = y - 2; yy <= y + 2; yy++) {
					if (max(abs(x - xx), abs(y - yy)) & 1) continue;
					ll t = ((ll)xx * (ll)INF) + 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 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 1 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 460 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 460 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 2 ms 460 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 5 ms 844 KB Output is correct
20 Correct 6 ms 844 KB Output is correct
21 Correct 6 ms 792 KB Output is correct
22 Correct 34 ms 5940 KB Output is correct
23 Correct 41 ms 5612 KB Output is correct
24 Correct 41 ms 5596 KB Output is correct
25 Correct 35 ms 5852 KB Output is correct
26 Correct 42 ms 5520 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 28916 KB Output is correct
2 Correct 317 ms 29980 KB Output is correct
3 Correct 276 ms 27132 KB Output is correct
4 Correct 275 ms 27256 KB Output is correct
5 Correct 624 ms 42572 KB Output is correct
6 Correct 2552 ms 125940 KB Output is correct
7 Correct 716 ms 40104 KB Output is correct
8 Correct 1219 ms 62496 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1807 ms 97016 KB Output is correct
3 Execution timed out 3073 ms 334020 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3053 ms 456852 KB Time limit exceeded
2 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 1 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 460 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 460 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 2 ms 460 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 5 ms 844 KB Output is correct
20 Correct 6 ms 844 KB Output is correct
21 Correct 6 ms 792 KB Output is correct
22 Correct 34 ms 5940 KB Output is correct
23 Correct 41 ms 5612 KB Output is correct
24 Correct 41 ms 5596 KB Output is correct
25 Correct 35 ms 5852 KB Output is correct
26 Correct 42 ms 5520 KB Output is correct
27 Correct 10 ms 1356 KB Output is correct
28 Correct 10 ms 1356 KB Output is correct
29 Correct 10 ms 1228 KB Output is correct
30 Correct 91 ms 11960 KB Output is correct
31 Correct 138 ms 11612 KB Output is correct
32 Correct 94 ms 11108 KB Output is correct
33 Correct 81 ms 7976 KB Output is correct
34 Correct 91 ms 9260 KB Output is correct
35 Correct 102 ms 9340 KB Output is correct
36 Correct 1906 ms 103904 KB Output is correct
37 Correct 1871 ms 101324 KB Output is correct
38 Correct 1852 ms 105384 KB Output is correct
39 Correct 1192 ms 31100 KB Output is correct
40 Correct 1225 ms 30956 KB Output is correct
41 Correct 1259 ms 31004 KB Output is correct
42 Correct 580 ms 35384 KB Output is correct
43 Correct 1027 ms 155204 KB Output is correct
44 Correct 1037 ms 155268 KB Output is correct
45 Correct 1065 ms 155204 KB Output is correct
46 Correct 1122 ms 155120 KB Output is correct
47 Correct 1040 ms 155416 KB Output is correct
48 Correct 1027 ms 155280 KB Output is correct
49 Correct 1038 ms 155372 KB Output is correct
50 Correct 1031 ms 155304 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 1 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 460 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 460 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 2 ms 460 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 5 ms 844 KB Output is correct
20 Correct 6 ms 844 KB Output is correct
21 Correct 6 ms 792 KB Output is correct
22 Correct 34 ms 5940 KB Output is correct
23 Correct 41 ms 5612 KB Output is correct
24 Correct 41 ms 5596 KB Output is correct
25 Correct 35 ms 5852 KB Output is correct
26 Correct 42 ms 5520 KB Output is correct
27 Correct 286 ms 28916 KB Output is correct
28 Correct 317 ms 29980 KB Output is correct
29 Correct 276 ms 27132 KB Output is correct
30 Correct 275 ms 27256 KB Output is correct
31 Correct 624 ms 42572 KB Output is correct
32 Correct 2552 ms 125940 KB Output is correct
33 Correct 716 ms 40104 KB Output is correct
34 Correct 1219 ms 62496 KB Output is correct
35 Correct 0 ms 332 KB Output is correct
36 Correct 1807 ms 97016 KB Output is correct
37 Execution timed out 3073 ms 334020 KB Time limit exceeded
38 Halted 0 ms 0 KB -