oj.uz

Submission #533440

# Submission time Handle Problem Language Result Execution time Memory
533440 2022-03-06T04:34:55 Z flappybird Circle selection (APIO18_circle_selection) C++17
64 / 100
 3000 ms 472096 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;
				int j;
				int ptr = 0;
				for (j = 0; j < mp[t].size(); j++) {
					int c = mp[t][j];
					if (!c) break;
					if (!ans[c] && chk(c, i)) ans[c] = i;
					if (ans[c]) mp[t][j] = 0;
					else mp[t][ptr] = c, ptr++;
				}
				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;
      |            ^~
circle_selection.cpp:79:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (j = 0; j < mp[t].size(); j++) {
      |                 ~~^~~~~~~~~~~~~~

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 320 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 328 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 324 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 452 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 452 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 4 ms 716 KB Output is correct
20 Correct 3 ms 736 KB Output is correct
21 Correct 4 ms 716 KB Output is correct
22 Correct 18 ms 4048 KB Output is correct
23 Correct 20 ms 4208 KB Output is correct
24 Correct 20 ms 3740 KB Output is correct
25 Correct 19 ms 3976 KB Output is correct
26 Correct 18 ms 4100 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 15700 KB Output is correct
2 Correct 184 ms 15244 KB Output is correct
3 Correct 188 ms 15048 KB Output is correct
4 Correct 160 ms 15116 KB Output is correct
5 Correct 231 ms 18160 KB Output is correct
6 Correct 939 ms 52800 KB Output is correct
7 Correct 236 ms 19484 KB Output is correct
8 Correct 369 ms 26260 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 839 ms 68288 KB Output is correct
3 Correct 2721 ms 178600 KB Output is correct
4 Correct 2722 ms 171356 KB Output is correct
5 Correct 2227 ms 144172 KB Output is correct
6 Correct 794 ms 67388 KB Output is correct
7 Correct 397 ms 55892 KB Output is correct
8 Correct 47 ms 9264 KB Output is correct
9 Correct 2812 ms 163856 KB Output is correct
10 Correct 1729 ms 136264 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2962 ms 470992 KB Output is correct
2 Execution timed out 3021 ms 472096 KB Time limit exceeded
3 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 320 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 328 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 324 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 452 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 452 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 4 ms 716 KB Output is correct
20 Correct 3 ms 736 KB Output is correct
21 Correct 4 ms 716 KB Output is correct
22 Correct 18 ms 4048 KB Output is correct
23 Correct 20 ms 4208 KB Output is correct
24 Correct 20 ms 3740 KB Output is correct
25 Correct 19 ms 3976 KB Output is correct
26 Correct 18 ms 4100 KB Output is correct
27 Correct 8 ms 1228 KB Output is correct
28 Correct 7 ms 1088 KB Output is correct
29 Correct 7 ms 1100 KB Output is correct
30 Correct 56 ms 8512 KB Output is correct
31 Correct 39 ms 8428 KB Output is correct
32 Correct 35 ms 7228 KB Output is correct
33 Correct 62 ms 6580 KB Output is correct
34 Correct 57 ms 6412 KB Output is correct
35 Correct 59 ms 6572 KB Output is correct
36 Correct 855 ms 74240 KB Output is correct
37 Correct 897 ms 67292 KB Output is correct
38 Correct 820 ms 75036 KB Output is correct
39 Correct 523 ms 11852 KB Output is correct
40 Correct 581 ms 12028 KB Output is correct
41 Correct 601 ms 12052 KB Output is correct
42 Correct 117 ms 11348 KB Output is correct
43 Correct 766 ms 134308 KB Output is correct
44 Correct 932 ms 134632 KB Output is correct
45 Correct 759 ms 134292 KB Output is correct
46 Correct 853 ms 134416 KB Output is correct
47 Correct 769 ms 134536 KB Output is correct
48 Correct 760 ms 134496 KB Output is correct
49 Correct 759 ms 134496 KB Output is correct
50 Correct 748 ms 134384 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 320 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 328 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 324 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 452 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 452 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 4 ms 716 KB Output is correct
20 Correct 3 ms 736 KB Output is correct
21 Correct 4 ms 716 KB Output is correct
22 Correct 18 ms 4048 KB Output is correct
23 Correct 20 ms 4208 KB Output is correct
24 Correct 20 ms 3740 KB Output is correct
25 Correct 19 ms 3976 KB Output is correct
26 Correct 18 ms 4100 KB Output is correct
27 Correct 176 ms 15700 KB Output is correct
28 Correct 184 ms 15244 KB Output is correct
29 Correct 188 ms 15048 KB Output is correct
30 Correct 160 ms 15116 KB Output is correct
31 Correct 231 ms 18160 KB Output is correct
32 Correct 939 ms 52800 KB Output is correct
33 Correct 236 ms 19484 KB Output is correct
34 Correct 369 ms 26260 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 839 ms 68288 KB Output is correct
37 Correct 2721 ms 178600 KB Output is correct
38 Correct 2722 ms 171356 KB Output is correct
39 Correct 2227 ms 144172 KB Output is correct
40 Correct 794 ms 67388 KB Output is correct
41 Correct 397 ms 55892 KB Output is correct
42 Correct 47 ms 9264 KB Output is correct
43 Correct 2812 ms 163856 KB Output is correct
44 Correct 1729 ms 136264 KB Output is correct
45 Correct 2962 ms 470992 KB Output is correct
46 Execution timed out 3021 ms 472096 KB Time limit exceeded
47 Halted 0 ms 0 KB -