oj.uz

Submission #533442

# Submission time Handle Problem Language Result Execution time Memory
533442 2022-03-06T04:48:11 Z flappybird Circle selection (APIO18_circle_selection) C++17
64 / 100
 3000 ms 467792 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O0")
#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];
inline 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;
}
unordered_map<ll, vector<int>> mp;
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 / 2) continue;
		mp.clear();
		e = 0;
		for (i = s; i <= N; i++) {
			if (ans[i]) continue;
			int x, y;
			x = X[i] >> k;
			y = Y[i] >> k;
			if (R[i] < r / 2 && !e) e = i - 1;
			int xx, yy;
			mp[((ll)x << 31LL) + y].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 = ((ll)xx << 31LL) + yy;
				vector<int> v;
				if (abs(x - xx) <= 1 && abs(y - yy) <= 1) {
					for (auto c : mp[t]) {
						if (!ans[c] && chk(c, i)) ans[c] = i;
						if (!ans[c]) v.push_back(c);
					}
					mp[t] = v;
				}
				else {
					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;
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:64:8: warning: unused variable 'xx' [-Wunused-variable]
   64 |    int xx, yy;
      |        ^~
circle_selection.cpp:64:12: warning: unused variable 'yy' [-Wunused-variable]
   64 |    int xx, yy;
      |            ^~

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 320 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 320 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 332 KB Output is correct
12 Correct 1 ms 448 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 372 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 3 ms 716 KB Output is correct
20 Correct 3 ms 716 KB Output is correct
21 Correct 3 ms 680 KB Output is correct
22 Correct 18 ms 4048 KB Output is correct
23 Correct 20 ms 4188 KB Output is correct
24 Correct 20 ms 3752 KB Output is correct
25 Correct 25 ms 3968 KB Output is correct
26 Correct 17 ms 4160 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 15824 KB Output is correct
2 Correct 146 ms 15192 KB Output is correct
3 Correct 172 ms 15180 KB Output is correct
4 Correct 148 ms 14976 KB Output is correct
5 Correct 174 ms 17952 KB Output is correct
6 Correct 890 ms 52772 KB Output is correct
7 Correct 248 ms 19464 KB Output is correct
8 Correct 318 ms 26556 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 900 ms 68288 KB Output is correct
3 Correct 2796 ms 178712 KB Output is correct
4 Correct 2782 ms 171524 KB Output is correct
5 Correct 2308 ms 144048 KB Output is correct
6 Correct 867 ms 67260 KB Output is correct
7 Correct 456 ms 55888 KB Output is correct
8 Correct 41 ms 9140 KB Output is correct
9 Correct 2946 ms 163780 KB Output is correct
10 Correct 1728 ms 136180 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3106 ms 467792 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 320 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 320 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 332 KB Output is correct
12 Correct 1 ms 448 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 372 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 3 ms 716 KB Output is correct
20 Correct 3 ms 716 KB Output is correct
21 Correct 3 ms 680 KB Output is correct
22 Correct 18 ms 4048 KB Output is correct
23 Correct 20 ms 4188 KB Output is correct
24 Correct 20 ms 3752 KB Output is correct
25 Correct 25 ms 3968 KB Output is correct
26 Correct 17 ms 4160 KB Output is correct
27 Correct 8 ms 844 KB Output is correct
28 Correct 6 ms 872 KB Output is correct
29 Correct 8 ms 844 KB Output is correct
30 Correct 50 ms 8224 KB Output is correct
31 Correct 40 ms 8160 KB Output is correct
32 Correct 36 ms 6904 KB Output is correct
33 Correct 51 ms 4956 KB Output is correct
34 Correct 66 ms 4892 KB Output is correct
35 Correct 64 ms 5052 KB Output is correct
36 Correct 853 ms 72616 KB Output is correct
37 Correct 890 ms 65652 KB Output is correct
38 Correct 869 ms 73472 KB Output is correct
39 Correct 228 ms 11056 KB Output is correct
40 Correct 197 ms 10992 KB Output is correct
41 Correct 217 ms 11016 KB Output is correct
42 Correct 113 ms 10228 KB Output is correct
43 Correct 799 ms 132800 KB Output is correct
44 Correct 947 ms 132932 KB Output is correct
45 Correct 786 ms 132840 KB Output is correct
46 Correct 907 ms 132940 KB Output is correct
47 Correct 790 ms 133044 KB Output is correct
48 Correct 798 ms 133052 KB Output is correct
49 Correct 780 ms 133092 KB Output is correct
50 Correct 783 ms 132896 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 320 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 320 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 332 KB Output is correct
12 Correct 1 ms 448 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 372 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 3 ms 716 KB Output is correct
20 Correct 3 ms 716 KB Output is correct
21 Correct 3 ms 680 KB Output is correct
22 Correct 18 ms 4048 KB Output is correct
23 Correct 20 ms 4188 KB Output is correct
24 Correct 20 ms 3752 KB Output is correct
25 Correct 25 ms 3968 KB Output is correct
26 Correct 17 ms 4160 KB Output is correct
27 Correct 163 ms 15824 KB Output is correct
28 Correct 146 ms 15192 KB Output is correct
29 Correct 172 ms 15180 KB Output is correct
30 Correct 148 ms 14976 KB Output is correct
31 Correct 174 ms 17952 KB Output is correct
32 Correct 890 ms 52772 KB Output is correct
33 Correct 248 ms 19464 KB Output is correct
34 Correct 318 ms 26556 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 900 ms 68288 KB Output is correct
37 Correct 2796 ms 178712 KB Output is correct
38 Correct 2782 ms 171524 KB Output is correct
39 Correct 2308 ms 144048 KB Output is correct
40 Correct 867 ms 67260 KB Output is correct
41 Correct 456 ms 55888 KB Output is correct
42 Correct 41 ms 9140 KB Output is correct
43 Correct 2946 ms 163780 KB Output is correct
44 Correct 1728 ms 136180 KB Output is correct
45 Execution timed out 3106 ms 467792 KB Time limit exceeded
46 Halted 0 ms 0 KB -