oj.uz

Submission #533399

# Submission time Handle Problem Language Result Execution time Memory
533399 2022-03-05T21:22:50 Z flappybird Circle selection (APIO18_circle_selection) C++14
19 / 100
 3000 ms 456604 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#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];
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;
}
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) continue;
		unordered_map<ll, list<int>> mp;
		e = 0;
		for (i = s; i <= N; i++) {
			if (ans[i]) continue;
			int x, y;
			x = X[i] / r;
			y = Y[i] / r;
			if (R[i] < r && !e) e = i - 1;
			int xx, yy;
			if (R[i] <= r) {
				for (xx = x - 1; xx <= x + 1; xx++) for (yy = y - 1; yy <= y + 1; yy++) mp[((ll)xx * (ll)INF) + yy].push_back(i);
			}
			else {
				for (xx = x - 2; xx <= x + 2; xx++) for (yy = y - 2; yy <= y + 2; yy++) if (!(max(abs(x - xx), abs(y - yy)) & 1)) mp[((ll)xx * (ll)INF) + yy].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;
			if (R[i] <= r) {
				for (xx = x - 1; xx <= x + 1; xx++) for (yy = y - 1; yy <= y + 1; yy++) {
					ll t = ((ll)xx * (ll)INF) + yy;
					list<int>::iterator pv = mp[t].end();
					for (auto it = mp[t].begin(); it != mp[t].end(); it++) {
						if (pv != mp[t].end()) mp[t].erase(pv), pv = mp[t].end();
						if (!ans[*it] && chk(*it, i)) ans[*it] = i, pv = it;
						if (ans[*it]) pv = it;
					}
					if (pv != mp[t].end()) mp[t].erase(pv), pv = mp[t].end();
					while (mp[t].size() && ans[mp[t].back()]) mp[t].pop_back();
				}
			}
			else {
				for (xx = x - 2; xx <= x + 2; xx++) for (yy = y - 2; yy <= y + 2; yy++) {
					if (max(abs(x - xx), abs(y - yy)) & 1) continue;
					ll t = ((ll)xx * (ll)INF) + yy;
					list<int>::iterator pv = mp[t].end();
					for (auto it = mp[t].begin(); it != mp[t].end(); it++) {
						if (pv != mp[t].end()) mp[t].erase(pv), pv = mp[t].end();
						if (!ans[*it] && chk(*it, i)) ans[*it] = i, pv = it;
						if (ans[*it]) pv = it;
					}
					if (pv != mp[t].end()) mp[t].erase(pv), pv = mp[t].end();
					while (mp[t].size() && ans[mp[t].back()]) mp[t].pop_back();
				}
			}
		}
	}
	for (i = 1; i <= N; i++) ri[ind[i]] = i;
	for (i = 1; i <= N; i++) cout << ind[ans[ri[i]]] << bb;
}

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 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 1 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 460 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 460 KB Output is correct
16 Correct 2 ms 716 KB Output is correct
17 Correct 2 ms 716 KB Output is correct
18 Correct 2 ms 716 KB Output is correct
19 Correct 6 ms 2124 KB Output is correct
20 Correct 11 ms 2536 KB Output is correct
21 Correct 7 ms 2252 KB Output is correct
22 Correct 44 ms 5980 KB Output is correct
23 Correct 46 ms 5700 KB Output is correct
24 Correct 42 ms 5556 KB Output is correct
25 Correct 42 ms 5876 KB Output is correct
26 Correct 44 ms 5560 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 631 ms 130616 KB Output is correct
2 Correct 731 ms 135520 KB Output is correct
3 Correct 620 ms 118584 KB Output is correct
4 Correct 577 ms 126532 KB Output is correct
5 Correct 1269 ms 128304 KB Output is correct
6 Correct 2982 ms 181596 KB Output is correct
7 Correct 1300 ms 108980 KB Output is correct
8 Correct 1653 ms 140736 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1958 ms 98220 KB Output is correct
3 Execution timed out 3088 ms 334020 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3111 ms 456604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
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 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 1 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 460 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 460 KB Output is correct
16 Correct 2 ms 716 KB Output is correct
17 Correct 2 ms 716 KB Output is correct
18 Correct 2 ms 716 KB Output is correct
19 Correct 6 ms 2124 KB Output is correct
20 Correct 11 ms 2536 KB Output is correct
21 Correct 7 ms 2252 KB Output is correct
22 Correct 44 ms 5980 KB Output is correct
23 Correct 46 ms 5700 KB Output is correct
24 Correct 42 ms 5556 KB Output is correct
25 Correct 42 ms 5876 KB Output is correct
26 Correct 44 ms 5560 KB Output is correct
27 Correct 19 ms 3916 KB Output is correct
28 Correct 15 ms 4428 KB Output is correct
29 Correct 14 ms 4144 KB Output is correct
30 Correct 97 ms 12072 KB Output is correct
31 Correct 111 ms 11592 KB Output is correct
32 Correct 104 ms 11088 KB Output is correct
33 Correct 119 ms 33588 KB Output is correct
34 Correct 179 ms 40500 KB Output is correct
35 Correct 302 ms 39544 KB Output is correct
36 Correct 1973 ms 104828 KB Output is correct
37 Correct 1896 ms 100424 KB Output is correct
38 Correct 2057 ms 105368 KB Output is correct
39 Execution timed out 3092 ms 31512 KB Time limit exceeded
40 Halted 0 ms 0 KB -

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 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 1 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 460 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 460 KB Output is correct
16 Correct 2 ms 716 KB Output is correct
17 Correct 2 ms 716 KB Output is correct
18 Correct 2 ms 716 KB Output is correct
19 Correct 6 ms 2124 KB Output is correct
20 Correct 11 ms 2536 KB Output is correct
21 Correct 7 ms 2252 KB Output is correct
22 Correct 44 ms 5980 KB Output is correct
23 Correct 46 ms 5700 KB Output is correct
24 Correct 42 ms 5556 KB Output is correct
25 Correct 42 ms 5876 KB Output is correct
26 Correct 44 ms 5560 KB Output is correct
27 Correct 631 ms 130616 KB Output is correct
28 Correct 731 ms 135520 KB Output is correct
29 Correct 620 ms 118584 KB Output is correct
30 Correct 577 ms 126532 KB Output is correct
31 Correct 1269 ms 128304 KB Output is correct
32 Correct 2982 ms 181596 KB Output is correct
33 Correct 1300 ms 108980 KB Output is correct
34 Correct 1653 ms 140736 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 1958 ms 98220 KB Output is correct
37 Execution timed out 3088 ms 334020 KB Time limit exceeded
38 Halted 0 ms 0 KB -