oj.uz

Submission #533392

# Submission time Handle Problem Language Result Execution time Memory
533392 2022-03-05T21:00:13 Z flappybird Circle selection (APIO18_circle_selection) C++14
49 / 100
 3000 ms 464300 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#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];
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[trans(xx, 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[trans(xx, 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 = trans(xx, 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 = trans(xx, 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 1 ms 252 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 460 KB Output is correct
12 Correct 2 ms 332 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 1 ms 460 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 5 ms 844 KB Output is correct
20 Correct 5 ms 924 KB Output is correct
21 Correct 5 ms 896 KB Output is correct
22 Correct 34 ms 5944 KB Output is correct
23 Correct 39 ms 5696 KB Output is correct
24 Correct 42 ms 5596 KB Output is correct
25 Correct 32 ms 5852 KB Output is correct
26 Correct 38 ms 5528 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 28964 KB Output is correct
2 Correct 242 ms 29988 KB Output is correct
3 Correct 238 ms 27236 KB Output is correct
4 Correct 221 ms 27272 KB Output is correct
5 Correct 504 ms 42644 KB Output is correct
6 Correct 2500 ms 125860 KB Output is correct
7 Correct 685 ms 40176 KB Output is correct
8 Correct 1071 ms 62496 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1764 ms 97000 KB Output is correct
3 Execution timed out 3104 ms 333824 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2989 ms 456708 KB Output is correct
2 Correct 1537 ms 252300 KB Output is correct
3 Correct 1514 ms 77316 KB Output is correct
4 Execution timed out 3039 ms 464300 KB Time limit exceeded
5 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 1 ms 252 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 460 KB Output is correct
12 Correct 2 ms 332 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 1 ms 460 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 5 ms 844 KB Output is correct
20 Correct 5 ms 924 KB Output is correct
21 Correct 5 ms 896 KB Output is correct
22 Correct 34 ms 5944 KB Output is correct
23 Correct 39 ms 5696 KB Output is correct
24 Correct 42 ms 5596 KB Output is correct
25 Correct 32 ms 5852 KB Output is correct
26 Correct 38 ms 5528 KB Output is correct
27 Correct 7 ms 1356 KB Output is correct
28 Correct 11 ms 1384 KB Output is correct
29 Correct 11 ms 1228 KB Output is correct
30 Correct 91 ms 12008 KB Output is correct
31 Correct 133 ms 11544 KB Output is correct
32 Correct 108 ms 11060 KB Output is correct
33 Correct 73 ms 8116 KB Output is correct
34 Correct 79 ms 9352 KB Output is correct
35 Correct 79 ms 9380 KB Output is correct
36 Correct 1832 ms 103880 KB Output is correct
37 Correct 1777 ms 101416 KB Output is correct
38 Correct 1819 ms 105484 KB Output is correct
39 Correct 791 ms 30980 KB Output is correct
40 Correct 817 ms 30984 KB Output is correct
41 Correct 853 ms 30996 KB Output is correct
42 Correct 530 ms 35416 KB Output is correct
43 Correct 960 ms 155312 KB Output is correct
44 Correct 1020 ms 155328 KB Output is correct
45 Correct 1059 ms 155092 KB Output is correct
46 Correct 1042 ms 155132 KB Output is correct
47 Correct 1060 ms 155288 KB Output is correct
48 Correct 960 ms 155248 KB Output is correct
49 Correct 958 ms 155476 KB Output is correct
50 Correct 994 ms 155220 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 1 ms 252 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 460 KB Output is correct
12 Correct 2 ms 332 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 1 ms 460 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 5 ms 844 KB Output is correct
20 Correct 5 ms 924 KB Output is correct
21 Correct 5 ms 896 KB Output is correct
22 Correct 34 ms 5944 KB Output is correct
23 Correct 39 ms 5696 KB Output is correct
24 Correct 42 ms 5596 KB Output is correct
25 Correct 32 ms 5852 KB Output is correct
26 Correct 38 ms 5528 KB Output is correct
27 Correct 249 ms 28964 KB Output is correct
28 Correct 242 ms 29988 KB Output is correct
29 Correct 238 ms 27236 KB Output is correct
30 Correct 221 ms 27272 KB Output is correct
31 Correct 504 ms 42644 KB Output is correct
32 Correct 2500 ms 125860 KB Output is correct
33 Correct 685 ms 40176 KB Output is correct
34 Correct 1071 ms 62496 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 1764 ms 97000 KB Output is correct
37 Execution timed out 3104 ms 333824 KB Time limit exceeded
38 Halted 0 ms 0 KB -