oj.uz

Submission #533379

# Submission time Handle Problem Language Result Execution time Memory
533379 2022-03-05T19:14:12 Z flappybird Circle selection (APIO18_circle_selection) C++17
37 / 100
 3000 ms 692672 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;
}
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;
}
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++) {
			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++) 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;
			for (xx = x - 2; xx <= x + 2; xx++) for (yy = y - 2; yy <= y + 2; yy++) {
				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 1 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 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 2 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 2 ms 460 KB Output is correct
17 Correct 3 ms 460 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 9 ms 1100 KB Output is correct
20 Correct 8 ms 972 KB Output is correct
21 Correct 8 ms 968 KB Output is correct
22 Correct 41 ms 7312 KB Output is correct
23 Correct 43 ms 7128 KB Output is correct
24 Correct 38 ms 6544 KB Output is correct
25 Correct 37 ms 7096 KB Output is correct
26 Correct 46 ms 6848 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 33292 KB Output is correct
2 Correct 394 ms 34860 KB Output is correct
3 Correct 412 ms 32116 KB Output is correct
4 Correct 391 ms 32152 KB Output is correct
5 Correct 1194 ms 47792 KB Output is correct
6 Execution timed out 3090 ms 185528 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 1680 ms 122192 KB Output is correct
3 Execution timed out 3090 ms 399556 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 3096 ms 692672 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 1 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 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 2 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 2 ms 460 KB Output is correct
17 Correct 3 ms 460 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 9 ms 1100 KB Output is correct
20 Correct 8 ms 972 KB Output is correct
21 Correct 8 ms 968 KB Output is correct
22 Correct 41 ms 7312 KB Output is correct
23 Correct 43 ms 7128 KB Output is correct
24 Correct 38 ms 6544 KB Output is correct
25 Correct 37 ms 7096 KB Output is correct
26 Correct 46 ms 6848 KB Output is correct
27 Correct 19 ms 1760 KB Output is correct
28 Correct 16 ms 1792 KB Output is correct
29 Correct 16 ms 1740 KB Output is correct
30 Correct 101 ms 15324 KB Output is correct
31 Correct 108 ms 14880 KB Output is correct
32 Correct 98 ms 13496 KB Output is correct
33 Correct 154 ms 13580 KB Output is correct
34 Correct 142 ms 10964 KB Output is correct
35 Correct 161 ms 10996 KB Output is correct
36 Correct 2005 ms 151700 KB Output is correct
37 Correct 1705 ms 117068 KB Output is correct
38 Correct 2001 ms 151816 KB Output is correct
39 Correct 1134 ms 47108 KB Output is correct
40 Correct 1150 ms 47000 KB Output is correct
41 Correct 1136 ms 47304 KB Output is correct
42 Correct 563 ms 45612 KB Output is correct
43 Correct 941 ms 211584 KB Output is correct
44 Correct 948 ms 211820 KB Output is correct
45 Correct 949 ms 211944 KB Output is correct
46 Correct 1004 ms 211788 KB Output is correct
47 Correct 956 ms 211932 KB Output is correct
48 Correct 952 ms 211872 KB Output is correct
49 Correct 956 ms 211984 KB Output is correct
50 Correct 960 ms 211780 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 1 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 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 2 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 2 ms 460 KB Output is correct
17 Correct 3 ms 460 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 9 ms 1100 KB Output is correct
20 Correct 8 ms 972 KB Output is correct
21 Correct 8 ms 968 KB Output is correct
22 Correct 41 ms 7312 KB Output is correct
23 Correct 43 ms 7128 KB Output is correct
24 Correct 38 ms 6544 KB Output is correct
25 Correct 37 ms 7096 KB Output is correct
26 Correct 46 ms 6848 KB Output is correct
27 Correct 402 ms 33292 KB Output is correct
28 Correct 394 ms 34860 KB Output is correct
29 Correct 412 ms 32116 KB Output is correct
30 Correct 391 ms 32152 KB Output is correct
31 Correct 1194 ms 47792 KB Output is correct
32 Execution timed out 3090 ms 185528 KB Time limit exceeded
33 Halted 0 ms 0 KB -