oj.uz

Submission #533456

# Submission time Handle Problem Language Result Execution time Memory
533456 2022-03-06T05:21:21 Z jjang36524 Circle selection (APIO18_circle_selection) C++14
64 / 100
 3000 ms 471524 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] >>k;
			y = Y[i] >>k;
			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 0 ms 332 KB Output is correct
2 Correct 0 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 0 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 332 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 2 ms 332 KB Output is correct
19 Correct 3 ms 616 KB Output is correct
20 Correct 3 ms 588 KB Output is correct
21 Correct 3 ms 588 KB Output is correct
22 Correct 17 ms 3932 KB Output is correct
23 Correct 26 ms 4092 KB Output is correct
24 Correct 18 ms 3624 KB Output is correct
25 Correct 17 ms 3792 KB Output is correct
26 Correct 15 ms 4008 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 15280 KB Output is correct
2 Correct 168 ms 14556 KB Output is correct
3 Correct 142 ms 14396 KB Output is correct
4 Correct 149 ms 14444 KB Output is correct
5 Correct 175 ms 17360 KB Output is correct
6 Correct 903 ms 52176 KB Output is correct
7 Correct 220 ms 19084 KB Output is correct
8 Correct 253 ms 26040 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 890 ms 67800 KB Output is correct
3 Correct 2721 ms 177972 KB Output is correct
4 Correct 2598 ms 171296 KB Output is correct
5 Correct 2183 ms 143900 KB Output is correct
6 Correct 756 ms 67140 KB Output is correct
7 Correct 394 ms 55836 KB Output is correct
8 Correct 41 ms 9120 KB Output is correct
9 Correct 2689 ms 163752 KB Output is correct
10 Correct 1637 ms 136084 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2916 ms 470372 KB Output is correct
2 Execution timed out 3034 ms 471524 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 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 0 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 332 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 2 ms 332 KB Output is correct
19 Correct 3 ms 616 KB Output is correct
20 Correct 3 ms 588 KB Output is correct
21 Correct 3 ms 588 KB Output is correct
22 Correct 17 ms 3932 KB Output is correct
23 Correct 26 ms 4092 KB Output is correct
24 Correct 18 ms 3624 KB Output is correct
25 Correct 17 ms 3792 KB Output is correct
26 Correct 15 ms 4008 KB Output is correct
27 Correct 5 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 8268 KB Output is correct
31 Correct 39 ms 8248 KB Output is correct
32 Correct 37 ms 7016 KB Output is correct
33 Correct 65 ms 4940 KB Output is correct
34 Correct 57 ms 4924 KB Output is correct
35 Correct 58 ms 5080 KB Output is correct
36 Correct 846 ms 72628 KB Output is correct
37 Correct 870 ms 65756 KB Output is correct
38 Correct 868 ms 73344 KB Output is correct
39 Correct 198 ms 10928 KB Output is correct
40 Correct 197 ms 11060 KB Output is correct
41 Correct 232 ms 10960 KB Output is correct
42 Correct 85 ms 10272 KB Output is correct
43 Correct 784 ms 132812 KB Output is correct
44 Correct 940 ms 132908 KB Output is correct
45 Correct 782 ms 132836 KB Output is correct
46 Correct 836 ms 132960 KB Output is correct
47 Correct 764 ms 133044 KB Output is correct
48 Correct 790 ms 133036 KB Output is correct
49 Correct 755 ms 133060 KB Output is correct
50 Correct 760 ms 132964 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 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 0 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 332 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 2 ms 332 KB Output is correct
19 Correct 3 ms 616 KB Output is correct
20 Correct 3 ms 588 KB Output is correct
21 Correct 3 ms 588 KB Output is correct
22 Correct 17 ms 3932 KB Output is correct
23 Correct 26 ms 4092 KB Output is correct
24 Correct 18 ms 3624 KB Output is correct
25 Correct 17 ms 3792 KB Output is correct
26 Correct 15 ms 4008 KB Output is correct
27 Correct 149 ms 15280 KB Output is correct
28 Correct 168 ms 14556 KB Output is correct
29 Correct 142 ms 14396 KB Output is correct
30 Correct 149 ms 14444 KB Output is correct
31 Correct 175 ms 17360 KB Output is correct
32 Correct 903 ms 52176 KB Output is correct
33 Correct 220 ms 19084 KB Output is correct
34 Correct 253 ms 26040 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 890 ms 67800 KB Output is correct
37 Correct 2721 ms 177972 KB Output is correct
38 Correct 2598 ms 171296 KB Output is correct
39 Correct 2183 ms 143900 KB Output is correct
40 Correct 756 ms 67140 KB Output is correct
41 Correct 394 ms 55836 KB Output is correct
42 Correct 41 ms 9120 KB Output is correct
43 Correct 2689 ms 163752 KB Output is correct
44 Correct 1637 ms 136084 KB Output is correct
45 Correct 2916 ms 470372 KB Output is correct
46 Execution timed out 3034 ms 471524 KB Time limit exceeded
47 Halted 0 ms 0 KB -