oj.uz

Submission #533438

# Submission time Handle Problem Language Result Execution time Memory
533438 2022-03-06T04:18:34 Z flappybird Circle selection (APIO18_circle_selection) C++17
100 / 100
 2822 ms 471288 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;
				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 0 ms 332 KB Output is correct
4 Correct 0 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 280 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 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 3 ms 716 KB Output is correct
20 Correct 4 ms 716 KB Output is correct
21 Correct 5 ms 664 KB Output is correct
22 Correct 15 ms 4052 KB Output is correct
23 Correct 18 ms 4188 KB Output is correct
24 Correct 17 ms 3752 KB Output is correct
25 Correct 18 ms 3932 KB Output is correct
26 Correct 16 ms 4188 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 16444 KB Output is correct
2 Correct 145 ms 15640 KB Output is correct
3 Correct 147 ms 15584 KB Output is correct
4 Correct 142 ms 15616 KB Output is correct
5 Correct 160 ms 18604 KB Output is correct
6 Correct 803 ms 53420 KB Output is correct
7 Correct 188 ms 19732 KB Output is correct
8 Correct 278 ms 26804 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 790 ms 68624 KB Output is correct
3 Correct 2467 ms 179324 KB Output is correct
4 Correct 2484 ms 179492 KB Output is correct
5 Correct 2059 ms 151816 KB Output is correct
6 Correct 710 ms 71396 KB Output is correct
7 Correct 366 ms 57880 KB Output is correct
8 Correct 42 ms 9436 KB Output is correct
9 Correct 2574 ms 171652 KB Output is correct
10 Correct 1593 ms 144404 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2799 ms 470248 KB Output is correct
2 Correct 2816 ms 471240 KB Output is correct
3 Correct 235 ms 21016 KB Output is correct
4 Correct 2822 ms 471132 KB Output is correct
5 Correct 2782 ms 471288 KB Output is correct
6 Correct 171 ms 17092 KB Output is correct

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 0 ms 332 KB Output is correct
4 Correct 0 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 280 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 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 3 ms 716 KB Output is correct
20 Correct 4 ms 716 KB Output is correct
21 Correct 5 ms 664 KB Output is correct
22 Correct 15 ms 4052 KB Output is correct
23 Correct 18 ms 4188 KB Output is correct
24 Correct 17 ms 3752 KB Output is correct
25 Correct 18 ms 3932 KB Output is correct
26 Correct 16 ms 4188 KB Output is correct
27 Correct 6 ms 844 KB Output is correct
28 Correct 5 ms 844 KB Output is correct
29 Correct 5 ms 844 KB Output is correct
30 Correct 38 ms 8224 KB Output is correct
31 Correct 39 ms 8252 KB Output is correct
32 Correct 35 ms 6932 KB Output is correct
33 Correct 51 ms 4976 KB Output is correct
34 Correct 58 ms 4960 KB Output is correct
35 Correct 50 ms 5036 KB Output is correct
36 Correct 753 ms 72688 KB Output is correct
37 Correct 788 ms 65772 KB Output is correct
38 Correct 771 ms 73464 KB Output is correct
39 Correct 192 ms 10980 KB Output is correct
40 Correct 175 ms 10960 KB Output is correct
41 Correct 197 ms 11056 KB Output is correct
42 Correct 78 ms 10324 KB Output is correct
43 Correct 714 ms 132840 KB Output is correct
44 Correct 868 ms 133108 KB Output is correct
45 Correct 689 ms 132812 KB Output is correct
46 Correct 807 ms 132896 KB Output is correct
47 Correct 717 ms 133048 KB Output is correct
48 Correct 741 ms 133148 KB Output is correct
49 Correct 701 ms 133196 KB Output is correct
50 Correct 706 ms 132912 KB Output is correct

Subtask #6
13.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 0 ms 332 KB Output is correct
4 Correct 0 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 280 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 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 3 ms 716 KB Output is correct
20 Correct 4 ms 716 KB Output is correct
21 Correct 5 ms 664 KB Output is correct
22 Correct 15 ms 4052 KB Output is correct
23 Correct 18 ms 4188 KB Output is correct
24 Correct 17 ms 3752 KB Output is correct
25 Correct 18 ms 3932 KB Output is correct
26 Correct 16 ms 4188 KB Output is correct
27 Correct 163 ms 16444 KB Output is correct
28 Correct 145 ms 15640 KB Output is correct
29 Correct 147 ms 15584 KB Output is correct
30 Correct 142 ms 15616 KB Output is correct
31 Correct 160 ms 18604 KB Output is correct
32 Correct 803 ms 53420 KB Output is correct
33 Correct 188 ms 19732 KB Output is correct
34 Correct 278 ms 26804 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 790 ms 68624 KB Output is correct
37 Correct 2467 ms 179324 KB Output is correct
38 Correct 2484 ms 179492 KB Output is correct
39 Correct 2059 ms 151816 KB Output is correct
40 Correct 710 ms 71396 KB Output is correct
41 Correct 366 ms 57880 KB Output is correct
42 Correct 42 ms 9436 KB Output is correct
43 Correct 2574 ms 171652 KB Output is correct
44 Correct 1593 ms 144404 KB Output is correct
45 Correct 2799 ms 470248 KB Output is correct
46 Correct 2816 ms 471240 KB Output is correct
47 Correct 235 ms 21016 KB Output is correct
48 Correct 2822 ms 471132 KB Output is correct
49 Correct 2782 ms 471288 KB Output is correct
50 Correct 171 ms 17092 KB Output is correct
51 Correct 6 ms 844 KB Output is correct
52 Correct 5 ms 844 KB Output is correct
53 Correct 5 ms 844 KB Output is correct
54 Correct 38 ms 8224 KB Output is correct
55 Correct 39 ms 8252 KB Output is correct
56 Correct 35 ms 6932 KB Output is correct
57 Correct 51 ms 4976 KB Output is correct
58 Correct 58 ms 4960 KB Output is correct
59 Correct 50 ms 5036 KB Output is correct
60 Correct 753 ms 72688 KB Output is correct
61 Correct 788 ms 65772 KB Output is correct
62 Correct 771 ms 73464 KB Output is correct
63 Correct 192 ms 10980 KB Output is correct
64 Correct 175 ms 10960 KB Output is correct
65 Correct 197 ms 11056 KB Output is correct
66 Correct 78 ms 10324 KB Output is correct
67 Correct 714 ms 132840 KB Output is correct
68 Correct 868 ms 133108 KB Output is correct
69 Correct 689 ms 132812 KB Output is correct
70 Correct 807 ms 132896 KB Output is correct
71 Correct 717 ms 133048 KB Output is correct
72 Correct 741 ms 133148 KB Output is correct
73 Correct 701 ms 133196 KB Output is correct
74 Correct 706 ms 132912 KB Output is correct
75 Correct 166 ms 23868 KB Output is correct
76 Correct 163 ms 23192 KB Output is correct
77 Correct 158 ms 23680 KB Output is correct
78 Correct 159 ms 23132 KB Output is correct
79 Correct 188 ms 23164 KB Output is correct
80 Correct 158 ms 22972 KB Output is correct
81 Correct 2694 ms 251012 KB Output is correct
82 Correct 2478 ms 247400 KB Output is correct
83 Correct 2485 ms 181348 KB Output is correct
84 Correct 2485 ms 182144 KB Output is correct
85 Correct 2547 ms 235348 KB Output is correct
86 Correct 2476 ms 244188 KB Output is correct
87 Correct 2371 ms 170456 KB Output is correct
88 Correct 717 ms 36504 KB Output is correct
89 Correct 677 ms 36572 KB Output is correct
90 Correct 700 ms 36524 KB Output is correct
91 Correct 701 ms 36580 KB Output is correct
92 Correct 688 ms 36620 KB Output is correct
93 Correct 2531 ms 191048 KB Output is correct
94 Correct 2351 ms 246932 KB Output is correct
95 Correct 2591 ms 234652 KB Output is correct
96 Correct 2590 ms 256088 KB Output is correct
97 Correct 2486 ms 247016 KB Output is correct
98 Correct 1014 ms 59792 KB Output is correct
99 Correct 2429 ms 185516 KB Output is correct
100 Correct 2599 ms 256660 KB Output is correct
101 Correct 1054 ms 76468 KB Output is correct
102 Correct 2265 ms 235080 KB Output is correct
103 Correct 2436 ms 234632 KB Output is correct
104 Correct 2466 ms 244868 KB Output is correct
105 Correct 369 ms 35972 KB Output is correct
106 Correct 1780 ms 316692 KB Output is correct
107 Correct 1763 ms 317152 KB Output is correct
108 Correct 2327 ms 316784 KB Output is correct
109 Correct 1854 ms 317212 KB Output is correct
110 Correct 1867 ms 316908 KB Output is correct
111 Correct 1724 ms 317128 KB Output is correct
112 Correct 1716 ms 316700 KB Output is correct
113 Correct 1865 ms 316888 KB Output is correct
114 Correct 1691 ms 317232 KB Output is correct
115 Correct 1729 ms 316964 KB Output is correct
116 Correct 1762 ms 316924 KB Output is correct