oj.uz

Submission #533441

# Submission time Handle Problem Language Result Execution time Memory
533441 2022-03-06T04:41:36 Z flappybird Circle selection (APIO18_circle_selection) C++17
64 / 100
 3000 ms 468976 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;
				for (auto c : mp[t]) {
					if (!ans[c] && chk(c, i)) ans[c] = i;
					if (!ans[c]) v.push_back(c);
				}
				v.swap(mp[t]);
			}
		}
	}
	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 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 0 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 332 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 456 KB Output is correct
16 Correct 2 ms 368 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 3 ms 720 KB Output is correct
20 Correct 3 ms 716 KB Output is correct
21 Correct 3 ms 716 KB Output is correct
22 Correct 24 ms 4008 KB Output is correct
23 Correct 19 ms 4196 KB Output is correct
24 Correct 20 ms 3764 KB Output is correct
25 Correct 21 ms 3932 KB Output is correct
26 Correct 22 ms 4104 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 17500 KB Output is correct
2 Correct 189 ms 16600 KB Output is correct
3 Correct 157 ms 16692 KB Output is correct
4 Correct 157 ms 16452 KB Output is correct
5 Correct 199 ms 18696 KB Output is correct
6 Correct 982 ms 53340 KB Output is correct
7 Correct 220 ms 19384 KB Output is correct
8 Correct 317 ms 25908 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 875 ms 69296 KB Output is correct
3 Correct 2895 ms 180200 KB Output is correct
4 Correct 2874 ms 171796 KB Output is correct
5 Correct 2347 ms 143476 KB Output is correct
6 Correct 844 ms 67028 KB Output is correct
7 Correct 446 ms 55852 KB Output is correct
8 Correct 47 ms 9468 KB Output is correct
9 Correct 2871 ms 164156 KB Output is correct
10 Correct 1799 ms 135144 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3062 ms 468976 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 1 ms 332 KB Output is correct
6 Correct 0 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 332 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 456 KB Output is correct
16 Correct 2 ms 368 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 3 ms 720 KB Output is correct
20 Correct 3 ms 716 KB Output is correct
21 Correct 3 ms 716 KB Output is correct
22 Correct 24 ms 4008 KB Output is correct
23 Correct 19 ms 4196 KB Output is correct
24 Correct 20 ms 3764 KB Output is correct
25 Correct 21 ms 3932 KB Output is correct
26 Correct 22 ms 4104 KB Output is correct
27 Correct 5 ms 972 KB Output is correct
28 Correct 5 ms 972 KB Output is correct
29 Correct 5 ms 972 KB Output is correct
30 Correct 52 ms 8384 KB Output is correct
31 Correct 43 ms 8280 KB Output is correct
32 Correct 41 ms 7132 KB Output is correct
33 Correct 56 ms 5440 KB Output is correct
34 Correct 69 ms 5452 KB Output is correct
35 Correct 56 ms 5544 KB Output is correct
36 Correct 876 ms 73188 KB Output is correct
37 Correct 926 ms 66272 KB Output is correct
38 Correct 881 ms 73872 KB Output is correct
39 Correct 274 ms 11072 KB Output is correct
40 Correct 266 ms 11128 KB Output is correct
41 Correct 316 ms 11116 KB Output is correct
42 Correct 139 ms 10672 KB Output is correct
43 Correct 832 ms 133184 KB Output is correct
44 Correct 986 ms 133208 KB Output is correct
45 Correct 811 ms 133208 KB Output is correct
46 Correct 916 ms 133212 KB Output is correct
47 Correct 832 ms 133336 KB Output is correct
48 Correct 825 ms 133292 KB Output is correct
49 Correct 806 ms 133508 KB Output is correct
50 Correct 802 ms 133316 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 1 ms 332 KB Output is correct
6 Correct 0 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 332 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 456 KB Output is correct
16 Correct 2 ms 368 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 3 ms 720 KB Output is correct
20 Correct 3 ms 716 KB Output is correct
21 Correct 3 ms 716 KB Output is correct
22 Correct 24 ms 4008 KB Output is correct
23 Correct 19 ms 4196 KB Output is correct
24 Correct 20 ms 3764 KB Output is correct
25 Correct 21 ms 3932 KB Output is correct
26 Correct 22 ms 4104 KB Output is correct
27 Correct 162 ms 17500 KB Output is correct
28 Correct 189 ms 16600 KB Output is correct
29 Correct 157 ms 16692 KB Output is correct
30 Correct 157 ms 16452 KB Output is correct
31 Correct 199 ms 18696 KB Output is correct
32 Correct 982 ms 53340 KB Output is correct
33 Correct 220 ms 19384 KB Output is correct
34 Correct 317 ms 25908 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 875 ms 69296 KB Output is correct
37 Correct 2895 ms 180200 KB Output is correct
38 Correct 2874 ms 171796 KB Output is correct
39 Correct 2347 ms 143476 KB Output is correct
40 Correct 844 ms 67028 KB Output is correct
41 Correct 446 ms 55852 KB Output is correct
42 Correct 47 ms 9468 KB Output is correct
43 Correct 2871 ms 164156 KB Output is correct
44 Correct 1799 ms 135144 KB Output is correct
45 Execution timed out 3062 ms 468976 KB Time limit exceeded
46 Halted 0 ms 0 KB -