oj.uz

Submission #533400

# Submission time Handle Problem Language Result Execution time Memory
533400 2022-03-05T21:33:47 Z flappybird Circle selection (APIO18_circle_selection) C++14
7 / 100
 3000 ms 456680 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, list<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 0 ms 332 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 1 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 332 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 2 ms 716 KB Output is correct
17 Correct 2 ms 716 KB Output is correct
18 Correct 2 ms 716 KB Output is correct
19 Correct 7 ms 2124 KB Output is correct
20 Correct 10 ms 2508 KB Output is correct
21 Correct 7 ms 2252 KB Output is correct
22 Correct 48 ms 5980 KB Output is correct
23 Correct 53 ms 5684 KB Output is correct
24 Correct 45 ms 5596 KB Output is correct
25 Correct 38 ms 5936 KB Output is correct
26 Correct 44 ms 5564 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 742 ms 130496 KB Output is correct
2 Correct 914 ms 135480 KB Output is correct
3 Correct 786 ms 118644 KB Output is correct
4 Correct 705 ms 126668 KB Output is correct
5 Correct 1300 ms 129076 KB Output is correct
6 Execution timed out 3041 ms 181528 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1928 ms 98224 KB Output is correct
3 Execution timed out 3110 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 3117 ms 456680 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 1 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 332 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 2 ms 716 KB Output is correct
17 Correct 2 ms 716 KB Output is correct
18 Correct 2 ms 716 KB Output is correct
19 Correct 7 ms 2124 KB Output is correct
20 Correct 10 ms 2508 KB Output is correct
21 Correct 7 ms 2252 KB Output is correct
22 Correct 48 ms 5980 KB Output is correct
23 Correct 53 ms 5684 KB Output is correct
24 Correct 45 ms 5596 KB Output is correct
25 Correct 38 ms 5936 KB Output is correct
26 Correct 44 ms 5564 KB Output is correct
27 Correct 12 ms 3916 KB Output is correct
28 Correct 19 ms 4396 KB Output is correct
29 Correct 13 ms 4172 KB Output is correct
30 Correct 96 ms 12116 KB Output is correct
31 Correct 117 ms 11632 KB Output is correct
32 Correct 93 ms 11168 KB Output is correct
33 Correct 121 ms 33616 KB Output is correct
34 Correct 213 ms 40500 KB Output is correct
35 Correct 378 ms 39524 KB Output is correct
36 Correct 1908 ms 104860 KB Output is correct
37 Correct 1859 ms 100292 KB Output is correct
38 Correct 1929 ms 105568 KB Output is correct
39 Execution timed out 3079 ms 31620 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 1 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 332 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 2 ms 716 KB Output is correct
17 Correct 2 ms 716 KB Output is correct
18 Correct 2 ms 716 KB Output is correct
19 Correct 7 ms 2124 KB Output is correct
20 Correct 10 ms 2508 KB Output is correct
21 Correct 7 ms 2252 KB Output is correct
22 Correct 48 ms 5980 KB Output is correct
23 Correct 53 ms 5684 KB Output is correct
24 Correct 45 ms 5596 KB Output is correct
25 Correct 38 ms 5936 KB Output is correct
26 Correct 44 ms 5564 KB Output is correct
27 Correct 742 ms 130496 KB Output is correct
28 Correct 914 ms 135480 KB Output is correct
29 Correct 786 ms 118644 KB Output is correct
30 Correct 705 ms 126668 KB Output is correct
31 Correct 1300 ms 129076 KB Output is correct
32 Execution timed out 3041 ms 181528 KB Time limit exceeded
33 Halted 0 ms 0 KB -