oj.uz

Submission #533397

# Submission time Handle Problem Language Result Execution time Memory
533397 2022-03-05T21:16:47 Z flappybird Circle selection (APIO18_circle_selection) C++14
49 / 100
 3000 ms 456636 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[((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;
					while (mp[t].size() && ans[mp[t].back()]) mp[t].pop_back();
				}
			}
			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;
					while (mp[t].size() && ans[mp[t].back()]) mp[t].pop_back();
				}
			}
		}
	}
	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 332 KB Output is correct
4 Correct 1 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 0 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 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 2 ms 460 KB Output is correct
17 Correct 2 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 7 ms 844 KB Output is correct
21 Correct 5 ms 844 KB Output is correct
22 Correct 39 ms 5996 KB Output is correct
23 Correct 51 ms 5740 KB Output is correct
24 Correct 43 ms 5640 KB Output is correct
25 Correct 43 ms 5876 KB Output is correct
26 Correct 44 ms 5484 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 28988 KB Output is correct
2 Correct 316 ms 30076 KB Output is correct
3 Correct 280 ms 27100 KB Output is correct
4 Correct 288 ms 27356 KB Output is correct
5 Correct 596 ms 42668 KB Output is correct
6 Correct 2645 ms 125748 KB Output is correct
7 Correct 695 ms 40096 KB Output is correct
8 Correct 1250 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 1967 ms 96996 KB Output is correct
3 Execution timed out 3114 ms 333764 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 3119 ms 456636 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 1 ms 332 KB Output is correct
4 Correct 1 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 0 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 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 2 ms 460 KB Output is correct
17 Correct 2 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 7 ms 844 KB Output is correct
21 Correct 5 ms 844 KB Output is correct
22 Correct 39 ms 5996 KB Output is correct
23 Correct 51 ms 5740 KB Output is correct
24 Correct 43 ms 5640 KB Output is correct
25 Correct 43 ms 5876 KB Output is correct
26 Correct 44 ms 5484 KB Output is correct
27 Correct 9 ms 1312 KB Output is correct
28 Correct 12 ms 1356 KB Output is correct
29 Correct 9 ms 1228 KB Output is correct
30 Correct 92 ms 11960 KB Output is correct
31 Correct 122 ms 11616 KB Output is correct
32 Correct 92 ms 11072 KB Output is correct
33 Correct 76 ms 8088 KB Output is correct
34 Correct 99 ms 9360 KB Output is correct
35 Correct 80 ms 9424 KB Output is correct
36 Correct 2052 ms 103848 KB Output is correct
37 Correct 1978 ms 101384 KB Output is correct
38 Correct 1996 ms 105508 KB Output is correct
39 Correct 900 ms 30992 KB Output is correct
40 Correct 882 ms 31052 KB Output is correct
41 Correct 901 ms 30936 KB Output is correct
42 Correct 613 ms 35436 KB Output is correct
43 Correct 1116 ms 155284 KB Output is correct
44 Correct 1140 ms 155232 KB Output is correct
45 Correct 1173 ms 155064 KB Output is correct
46 Correct 1182 ms 155140 KB Output is correct
47 Correct 1124 ms 155356 KB Output is correct
48 Correct 1159 ms 155324 KB Output is correct
49 Correct 1106 ms 155276 KB Output is correct
50 Correct 1175 ms 155252 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 332 KB Output is correct
4 Correct 1 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 0 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 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 2 ms 460 KB Output is correct
17 Correct 2 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 7 ms 844 KB Output is correct
21 Correct 5 ms 844 KB Output is correct
22 Correct 39 ms 5996 KB Output is correct
23 Correct 51 ms 5740 KB Output is correct
24 Correct 43 ms 5640 KB Output is correct
25 Correct 43 ms 5876 KB Output is correct
26 Correct 44 ms 5484 KB Output is correct
27 Correct 272 ms 28988 KB Output is correct
28 Correct 316 ms 30076 KB Output is correct
29 Correct 280 ms 27100 KB Output is correct
30 Correct 288 ms 27356 KB Output is correct
31 Correct 596 ms 42668 KB Output is correct
32 Correct 2645 ms 125748 KB Output is correct
33 Correct 695 ms 40096 KB Output is correct
34 Correct 1250 ms 62496 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 1967 ms 96996 KB Output is correct
37 Execution timed out 3114 ms 333764 KB Time limit exceeded
38 Halted 0 ms 0 KB -