oj.uz

Submission #317584

# Submission time Handle Problem Language Result Execution time Memory
317584 2020-10-30T03:29:16 Z Kevin_Zhang_TW Circle selection (APIO18_circle_selection) C++17
100 / 100
 1529 ms 48856 KB 
#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
void kout(){ cerr << endl; }
template<class T1, class ...T2> void kout(T1 a, T2 ...e) { cerr << a << ' ', kout(e...); }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 300010, MAX_K = 32;
int n;
ll up(ll v) { return v * v; }
int die[MAX_N];
struct cir {
	ll x, y, r, id;
	pair<int,int> div(int d) {
		return {x/d, y/d};
	}
	friend bool inter(cir a, cir b) {
		return up(a.x-b.x) + up(a.y-b.y) <= up(a.r+b.r);
	}
	bool operator < (cir a) {
		return make_pair(-r, id) < make_pair(-a.r, a.id);
	}
	bool set(cir killer) {
		if (die[id] != -1) 
			return true;
		if (inter(killer, *(this)))
			return die[id] = killer.id, true;
		return false;
	}
	bool dead() { return die[id] != -1; }
	friend istream& operator >> (istream& in, cir &a) {
		static int cnt;
		//const static ll dx = 12398291, dy = -23412845234;
		const static ll dx = 0, dy = 0;
		return a.id = cnt++, in >> a.x >> a.y >> a.r, a.x += dx, a.y += dy, in;
	}
}a[MAX_N];
void brute_force() {
	for (int i = 0;i < n;++i) {
		int id = a[i].id;
		if (~die[id]) continue;
		die[id] = id;
		for (int j = i+1;j < n;++j) 
			a[j].set(a[i]);
	}
}
//random_device rd;
//mt19937 gen(rd());
//uniform_int_
//struct hs {
//	size_t operator()(pair<int,int> a) const {
//		const static unsigned long long f = 9823419848328479ll;
//	   	return f * a.first - a.second + (a.first ^ a.second);
//	}
//};
//
//unordered_map<pair<int,int>, vector<int>, hs> mp[MAX_K];
struct allcir {
	vector<pair<int,vector<pair<int,int>>>> mp;
	ll block_size = 1ll << 31;
	void shrink(ll sz) {
		if (sz < block_size) 
			block_size = sz, putall();
	}
	void putall() {
		mp.clear();
		vector<pair< pair<int,int> , int > > allp;
		for (int i = 0;i < n;++i) if (!a[i].dead())
			allp.pb( a[i].div(block_size), i );
		sort(AI(allp));
		for (auto [P, id] : allp) {
			if (mp.empty() || P.first != mp.back().first)
				mp.pb(P.first, 0);
			mp.back().second.pb(P.second, id);
		}
		for (auto &[x, v] : mp)
			sort(AI(v));
	}
	void killall(cir a) {
		auto [x, y] = a.div(block_size);
		auto it = lower_bound(AI(mp), pair<int,vector<pair<int,int>>>{x-2, vector<pair<int,int>>{}});
		while (it != end(mp) && x + 2 >= it->first) {
			auto &vec = it->second;
			auto vit = lower_bound(AI(vec), pair<int,int>{ y - 2, -1});
			while (vit != end(vec) && y + 2 >= vit->first) 
				::a[vit->second].set(a), ++vit;
			++it;
		}
	}
}grid;
void solve_all() {
//	for (int i = 0;i < n;++i) {
//		for (int j = 0;j < MAX_K;++j) 
//			mp[j][ a[i].div(1ll<<j) ].pb(i);
//	}
	grid.putall();

	for (int i = 0;i < n;++i) {
		if (a[i].dead())
			continue;

		a[i].set(a[i]);

		int j = 0;
		while ((1ll<<j) < a[i].r)
			++j;

		grid.shrink(1ll << j);


		grid.killall(a[i]);
//		for (int r : {j}) {
//			grid.killall(a[i]);
//			auto &mp = ::mp[r];
//			auto [x, y] = a[i].div(1ll << r);
//			for (int nx : {x-2, x-1, x, x+1, x+2})
//				for (int ny : {y-2, y-1, y, y+1, y+2})
//					if (mp.count({nx, ny})) {
//						auto &V = mp[{nx, ny}];
//						vector<int> nv;
//						for (int j : V)
//							if (!a[j].set(a[i]))
//								nv.pb(j);
//						swap(nv, V);
//					}
//			break;
//		}
	}
}
//void testmap() {
//	mp.reserve(n * 10);
//	int rad = a[0].r ;
//	for (int i = 1;i < n;++i)
//		if (rad != a[i].r) exit(1);
//
//	rad <<= 1;
//
//	for (int i = 0;i < n;++i)
//		mp[ a[i].div(rad) ].pb(i);
//
//	for (int i = 0;i < n;++i) {
//		if (a[i].dead()) continue;
//		a[i].set(a[i]);
//		auto [x, y] = a[i].div(rad);
//
//		for (int nx : {x-1, x, x+1})
//			for (int ny : {y-1, y, y+1})
//				if (mp.count({nx, ny})) {
//					auto &V = mp[{nx, ny}];
//					vector<int> nv;
//					for (int j : V)
//						if (!a[j].set(a[i]))
//							nv.pb(j);
//					swap(nv, V);
//				}
//	}
//}
void solve() {
	sort(a, a+n);
	fill(die, die+n, -1);
	solve_all();
}
signed main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 0;i < n;++i)
		cin >> a[i];
	solve();
	for (int i = 0;i < n;++i)
		cout << die[i]+1 << " \n"[i+1==n];
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 512 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 7 ms 948 KB Output is correct
20 Correct 4 ms 948 KB Output is correct
21 Correct 4 ms 896 KB Output is correct
22 Correct 6 ms 948 KB Output is correct
23 Correct 7 ms 920 KB Output is correct
24 Correct 6 ms 968 KB Output is correct
25 Correct 6 ms 1204 KB Output is correct
26 Correct 7 ms 980 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 29796 KB Output is correct
2 Correct 256 ms 27736 KB Output is correct
3 Correct 255 ms 29140 KB Output is correct
4 Correct 232 ms 29648 KB Output is correct
5 Correct 287 ms 27092 KB Output is correct
6 Correct 357 ms 30808 KB Output is correct
7 Correct 310 ms 27348 KB Output is correct
8 Correct 302 ms 28244 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 150 ms 10144 KB Output is correct
3 Correct 469 ms 30676 KB Output is correct
4 Correct 481 ms 30680 KB Output is correct
5 Correct 513 ms 28648 KB Output is correct
6 Correct 226 ms 15336 KB Output is correct
7 Correct 105 ms 8720 KB Output is correct
8 Correct 18 ms 2348 KB Output is correct
9 Correct 516 ms 31188 KB Output is correct
10 Correct 479 ms 29572 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 30584 KB Output is correct
2 Correct 376 ms 48212 KB Output is correct
3 Correct 320 ms 28244 KB Output is correct
4 Correct 388 ms 48576 KB Output is correct
5 Correct 383 ms 48852 KB Output is correct
6 Correct 335 ms 30588 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 512 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 7 ms 948 KB Output is correct
20 Correct 4 ms 948 KB Output is correct
21 Correct 4 ms 896 KB Output is correct
22 Correct 6 ms 948 KB Output is correct
23 Correct 7 ms 920 KB Output is correct
24 Correct 6 ms 968 KB Output is correct
25 Correct 6 ms 1204 KB Output is correct
26 Correct 7 ms 980 KB Output is correct
27 Correct 8 ms 1432 KB Output is correct
28 Correct 8 ms 1528 KB Output is correct
29 Correct 8 ms 1400 KB Output is correct
30 Correct 12 ms 1400 KB Output is correct
31 Correct 14 ms 1656 KB Output is correct
32 Correct 13 ms 1528 KB Output is correct
33 Correct 78 ms 11064 KB Output is correct
34 Correct 79 ms 11064 KB Output is correct
35 Correct 89 ms 9836 KB Output is correct
36 Correct 148 ms 11444 KB Output is correct
37 Correct 142 ms 11440 KB Output is correct
38 Correct 151 ms 11316 KB Output is correct
39 Correct 439 ms 8636 KB Output is correct
40 Correct 421 ms 8520 KB Output is correct
41 Correct 441 ms 8528 KB Output is correct
42 Correct 99 ms 8888 KB Output is correct
43 Correct 113 ms 14408 KB Output is correct
44 Correct 109 ms 14408 KB Output is correct
45 Correct 111 ms 14376 KB Output is correct
46 Correct 111 ms 14520 KB Output is correct
47 Correct 110 ms 14408 KB Output is correct
48 Correct 110 ms 14404 KB Output is correct
49 Correct 113 ms 14552 KB Output is correct
50 Correct 115 ms 14408 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 512 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 7 ms 948 KB Output is correct
20 Correct 4 ms 948 KB Output is correct
21 Correct 4 ms 896 KB Output is correct
22 Correct 6 ms 948 KB Output is correct
23 Correct 7 ms 920 KB Output is correct
24 Correct 6 ms 968 KB Output is correct
25 Correct 6 ms 1204 KB Output is correct
26 Correct 7 ms 980 KB Output is correct
27 Correct 241 ms 29796 KB Output is correct
28 Correct 256 ms 27736 KB Output is correct
29 Correct 255 ms 29140 KB Output is correct
30 Correct 232 ms 29648 KB Output is correct
31 Correct 287 ms 27092 KB Output is correct
32 Correct 357 ms 30808 KB Output is correct
33 Correct 310 ms 27348 KB Output is correct
34 Correct 302 ms 28244 KB Output is correct
35 Correct 1 ms 384 KB Output is correct
36 Correct 150 ms 10144 KB Output is correct
37 Correct 469 ms 30676 KB Output is correct
38 Correct 481 ms 30680 KB Output is correct
39 Correct 513 ms 28648 KB Output is correct
40 Correct 226 ms 15336 KB Output is correct
41 Correct 105 ms 8720 KB Output is correct
42 Correct 18 ms 2348 KB Output is correct
43 Correct 516 ms 31188 KB Output is correct
44 Correct 479 ms 29572 KB Output is correct
45 Correct 371 ms 30584 KB Output is correct
46 Correct 376 ms 48212 KB Output is correct
47 Correct 320 ms 28244 KB Output is correct
48 Correct 388 ms 48576 KB Output is correct
49 Correct 383 ms 48852 KB Output is correct
50 Correct 335 ms 30588 KB Output is correct
51 Correct 8 ms 1432 KB Output is correct
52 Correct 8 ms 1528 KB Output is correct
53 Correct 8 ms 1400 KB Output is correct
54 Correct 12 ms 1400 KB Output is correct
55 Correct 14 ms 1656 KB Output is correct
56 Correct 13 ms 1528 KB Output is correct
57 Correct 78 ms 11064 KB Output is correct
58 Correct 79 ms 11064 KB Output is correct
59 Correct 89 ms 9836 KB Output is correct
60 Correct 148 ms 11444 KB Output is correct
61 Correct 142 ms 11440 KB Output is correct
62 Correct 151 ms 11316 KB Output is correct
63 Correct 439 ms 8636 KB Output is correct
64 Correct 421 ms 8520 KB Output is correct
65 Correct 441 ms 8528 KB Output is correct
66 Correct 99 ms 8888 KB Output is correct
67 Correct 113 ms 14408 KB Output is correct
68 Correct 109 ms 14408 KB Output is correct
69 Correct 111 ms 14376 KB Output is correct
70 Correct 111 ms 14520 KB Output is correct
71 Correct 110 ms 14408 KB Output is correct
72 Correct 110 ms 14404 KB Output is correct
73 Correct 113 ms 14552 KB Output is correct
74 Correct 115 ms 14408 KB Output is correct
75 Correct 291 ms 30252 KB Output is correct
76 Correct 269 ms 29664 KB Output is correct
77 Correct 255 ms 34004 KB Output is correct
78 Correct 239 ms 33748 KB Output is correct
79 Correct 390 ms 29528 KB Output is correct
80 Correct 246 ms 33748 KB Output is correct
81 Correct 500 ms 31676 KB Output is correct
82 Correct 464 ms 32084 KB Output is correct
83 Correct 477 ms 32472 KB Output is correct
84 Correct 467 ms 30932 KB Output is correct
85 Correct 469 ms 30420 KB Output is correct
86 Correct 470 ms 32088 KB Output is correct
87 Correct 495 ms 30764 KB Output is correct
88 Correct 1529 ms 26732 KB Output is correct
89 Correct 1348 ms 26624 KB Output is correct
90 Correct 1378 ms 26468 KB Output is correct
91 Correct 1360 ms 26640 KB Output is correct
92 Correct 1337 ms 26612 KB Output is correct
93 Correct 454 ms 48088 KB Output is correct
94 Correct 407 ms 30428 KB Output is correct
95 Correct 471 ms 48104 KB Output is correct
96 Correct 450 ms 48244 KB Output is correct
97 Correct 480 ms 27748 KB Output is correct
98 Correct 391 ms 32852 KB Output is correct
99 Correct 452 ms 48336 KB Output is correct
100 Correct 407 ms 47952 KB Output is correct
101 Correct 431 ms 29916 KB Output is correct
102 Correct 454 ms 48216 KB Output is correct
103 Correct 546 ms 27876 KB Output is correct
104 Correct 440 ms 47828 KB Output is correct
105 Correct 340 ms 27416 KB Output is correct
106 Correct 384 ms 41688 KB Output is correct
107 Correct 383 ms 41684 KB Output is correct
108 Correct 399 ms 41684 KB Output is correct
109 Correct 376 ms 41692 KB Output is correct
110 Correct 383 ms 41696 KB Output is correct
111 Correct 379 ms 41692 KB Output is correct
112 Correct 375 ms 41684 KB Output is correct
113 Correct 374 ms 41684 KB Output is correct
114 Correct 384 ms 41780 KB Output is correct
115 Correct 376 ms 41812 KB Output is correct
116 Correct 382 ms 48856 KB Output is correct