Submission #103225

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
103225	2019-03-29T08:55:48 Z	E869120	Circle selection (APIO18_circle_selection)	C++14	75 / 100	3000 ms	503024 KB

circle_selection

#include <iostream>
#include <vector>
#include <queue>
#include <ctime>
using namespace std;
#pragma warning (disable: 4996)

int cntv = 0;

struct Node {
	int val, l, r;
};

vector<Node>vec; vector<vector<int>>num;
Node BASE = { 0, -1, -1 };

class SegmentTree {
public:
	Node BASE; vector<int>V; unsigned int lx, ly, rx, ry; int size_;

	void init() {
		size_ = 1;
	}
	void add(long long px, long long py, int NN) {
		int cx = 0;
		for (int i = 61; i >= 0; i--) {
			vec[cx].val += 1;
			if ((i & 1) == 1) {
				int dep = (i >> 1);
				if (px >= (1LL << dep)) {
					if (vec[cx].r == -1) { vec[cx].r = size_; size_++; }
					cx = vec[cx].r; px -= (1LL << dep);
				}
				else {
					if (vec[cx].l == -1) { vec[cx].l = size_; size_++; }
					cx = vec[cx].l;
				}
			}
			else {
				int dep = (i >> 1);
				if (py >= (1LL << dep)) {
					if (vec[cx].r == -1) { vec[cx].r = size_; size_++; }
					cx = vec[cx].r; py -= (1LL << dep);
				}
				else {
					if (vec[cx].l == -1) { vec[cx].l = size_; size_++; }
					cx = vec[cx].l;
				}
			}
		}
		vec[cx].val++; num[cx].push_back(NN);
	}
	void lose(long long px, long long py, int NN) {
		int cx = 0;
		for (int i = 61; i >= 0; i--) {
			vec[cx].val -= 1;
			if ((i & 1) == 1) {
				int dep = (i >> 1);
				if (px >= (1LL << dep)) {
					if (vec[cx].r == -1) { vec[cx].r = size_; size_++; }
					cx = vec[cx].r; px -= (1LL << dep);
				}
				else {
					if (vec[cx].l == -1) { vec[cx].l = size_; size_++; }
					cx = vec[cx].l;
				}
			}
			else {
				int dep = (i >> 1);
				if (py >= (1LL << dep)) {
					if (vec[cx].r == -1) { vec[cx].r = size_; size_++; }
					cx = vec[cx].r; py -= (1LL << dep);
				}
				else {
					if (vec[cx].l == -1) { vec[cx].l = size_; size_++; }
					cx = vec[cx].l;
				}
			}
		}
		vec[cx].val--; num[cx].clear();
	}
	void query_(unsigned int ax, unsigned int ay, unsigned int bx, unsigned int by, int dep, int u) {
		if (vec[u].val == 0) return;
		if (rx <= ax || bx <= lx || ry <= ay || by <= ly) return;
		if (dep == 0) {
			for (int i : num[u]) V.push_back(i);
			return;
		}
		cntv++;
		if (dep % 2 == 0) {
			if (vec[u].l >= 0) query_(ax, ay, (ax + bx) >> 1, by, dep - 1, vec[u].l);
			if (vec[u].r >= 0) query_((ax + bx) >> 1, ay, bx, by, dep - 1, vec[u].r);
		}
		else {
			if (vec[u].l >= 0) query_(ax, ay, bx, (ay + by) >> 1, dep - 1, vec[u].l);
			if (vec[u].r >= 0) query_(ax, (ay + by) >> 1, bx, by, dep - 1, vec[u].r);
		}
	}
	vector<int> query(long long LX, long long LY, long long RX, long long RY) {
		LX = max(LX, 0LL); LY = max(LY, 0LL); RX = min(RX, (1LL << 31)); RY = min(RY, (1LL << 31));
		lx = LX; ly = LY; rx = RX; ry = RY;
		V.clear();
		query_(0, 0, (1LL << 31), (1LL << 31), 62, 0);
		return V;
	}
};

long long N, X[1 << 19], Y[1 << 19], R[1 << 19], score[1 << 19];
bool used[1 << 19];

long long dist(int p1, int p2) {
	return (X[p1] - X[p2]) * (X[p1] - X[p2]) + abs(Y[p1] - Y[p2]) * abs(Y[p1] - Y[p2]);
}

void solve_Jury() {
	while (true) {
		int maxn = -1, id = -1;
		for (int i = 1; i <= N; i++) {
			if (used[i] == true) continue;
			if (maxn < R[i]) { maxn = R[i]; id = i; }
		}

		if (id == -1) break;

		for (int i = 1; i <= N; i++) {
			if (used[i] == true) continue;
			if (dist(id, i) <= (R[i] + R[id]) * (R[i] + R[id])) { used[i] = true; score[i] = id; }
		}
	}
}

bool uses[1 << 19]; SegmentTree Z;

void solve_subtasks() {
	if (N <= 10000) { vec.resize(N * 64, BASE); num.resize(N * 64); }
	else if (N <= 100000) { vec.resize(N * 50, BASE); num.resize(N * 50); }
	else { vec.resize(N * 45, BASE); num.resize(N * 45); }

	priority_queue<pair<long long, int>, vector<pair<long long, int>>, less<pair<long long, int>>>Q;
	Z.init();
	for (int i = 1; i <= N; i++) Q.push(make_pair(R[i], -i));
	for (int i = 1; i <= N; i++) Z.add(X[i], Y[i], i);
	
	while (!Q.empty()) {
		int pos = -Q.top().second;
		vector<int>E = Z.query(X[pos] - 2LL * R[pos], Y[pos] - 2LL * R[pos], X[pos] + 2LL * R[pos] + 1LL, Y[pos] + 2LL * R[pos] + 1LL);
		
		for (int i = 0; i < E.size(); i++) {
			if (dist(pos, E[i]) <= 1LL * (R[pos] + R[E[i]]) * (R[pos] + R[E[i]])) {
				Z.lose(X[E[i]], Y[E[i]], E[i]);
				used[E[i]] = true;
				score[E[i]] = pos;
			}
		}
		while (!Q.empty()) { int pos = -Q.top().second; if (used[pos] == false) break; Q.pop(); }
	}
	return;
}

long long Rand() {
	long long s = 1, t = 0;
	for (int i = 0; i < 3; i++) { t += (rand() % 1024)*s; s *= 1024; }
	return t;
}

int main() {
	srand((unsigned)time(NULL));
	scanf("%lld", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%lld%lld%lld", &X[i], &Y[i], &R[i]);
		X[i] += (1LL << 30); Y[i] += (1LL << 30);
	}

	if (N <= 2) {
		solve_Jury();
	}

	else {
		solve_subtasks();
	}

	for (int i = 1; i <= N; i++) {
		if (i >= 2) printf(" ");
		printf("%lld", score[i]);
	}
	printf("\n");
	return 0;
}

Compilation message

circle_selection.cpp:6:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
circle_selection.cpp: In function 'void solve_subtasks()':
circle_selection.cpp:148:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < E.size(); i++) {
                   ~~^~~~~~~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:168:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &N);
  ~~~~~^~~~~~~~~~~~
circle_selection.cpp:170:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &X[i], &Y[i], &R[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	384 KB	Output is correct
2	Correct	3 ms	384 KB	Output is correct
3	Correct	3 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Correct	3 ms	640 KB	Output is correct
7	Correct	7 ms	640 KB	Output is correct
8	Correct	4 ms	640 KB	Output is correct
9	Correct	3 ms	640 KB	Output is correct
10	Correct	3 ms	640 KB	Output is correct
11	Correct	3 ms	640 KB	Output is correct
12	Correct	4 ms	640 KB	Output is correct
13	Correct	3 ms	640 KB	Output is correct
14	Correct	3 ms	640 KB	Output is correct
15	Correct	3 ms	640 KB	Output is correct
16	Correct	8 ms	2688 KB	Output is correct
17	Correct	6 ms	2688 KB	Output is correct
18	Correct	8 ms	2688 KB	Output is correct
19	Correct	35 ms	12156 KB	Output is correct
20	Correct	29 ms	12072 KB	Output is correct
21	Correct	33 ms	12072 KB	Output is correct
22	Correct	31 ms	12152 KB	Output is correct
23	Correct	31 ms	12032 KB	Output is correct
24	Correct	29 ms	12032 KB	Output is correct
25	Correct	30 ms	12032 KB	Output is correct
26	Correct	31 ms	12152 KB	Output is correct

Subtask #2

0 / 12.0

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

Subtask #3

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	384 KB	Output is correct
2	Correct	725 ms	184452 KB	Output is correct
3	Correct	2420 ms	499876 KB	Output is correct
4	Correct	2528 ms	499788 KB	Output is correct
5	Correct	2476 ms	486300 KB	Output is correct
6	Correct	1200 ms	260796 KB	Output is correct
7	Correct	528 ms	151912 KB	Output is correct
8	Correct	113 ms	31600 KB	Output is correct
9	Correct	2581 ms	499716 KB	Output is correct
10	Correct	2244 ms	499884 KB	Output is correct

Subtask #4

23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2053 ms	499700 KB	Output is correct
2	Correct	1946 ms	499684 KB	Output is correct
3	Correct	2063 ms	499696 KB	Output is correct
4	Correct	2146 ms	499708 KB	Output is correct
5	Correct	1936 ms	499828 KB	Output is correct
6	Correct	1965 ms	499756 KB	Output is correct

Subtask #5

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	384 KB	Output is correct
2	Correct	3 ms	384 KB	Output is correct
3	Correct	3 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Correct	3 ms	640 KB	Output is correct
7	Correct	7 ms	640 KB	Output is correct
8	Correct	4 ms	640 KB	Output is correct
9	Correct	3 ms	640 KB	Output is correct
10	Correct	3 ms	640 KB	Output is correct
11	Correct	3 ms	640 KB	Output is correct
12	Correct	4 ms	640 KB	Output is correct
13	Correct	3 ms	640 KB	Output is correct
14	Correct	3 ms	640 KB	Output is correct
15	Correct	3 ms	640 KB	Output is correct
16	Correct	8 ms	2688 KB	Output is correct
17	Correct	6 ms	2688 KB	Output is correct
18	Correct	8 ms	2688 KB	Output is correct
19	Correct	35 ms	12156 KB	Output is correct
20	Correct	29 ms	12072 KB	Output is correct
21	Correct	33 ms	12072 KB	Output is correct
22	Correct	31 ms	12152 KB	Output is correct
23	Correct	31 ms	12032 KB	Output is correct
24	Correct	29 ms	12032 KB	Output is correct
25	Correct	30 ms	12032 KB	Output is correct
26	Correct	31 ms	12152 KB	Output is correct
27	Correct	65 ms	23924 KB	Output is correct
28	Correct	71 ms	23848 KB	Output is correct
29	Correct	62 ms	23848 KB	Output is correct
30	Correct	60 ms	23796 KB	Output is correct
31	Correct	65 ms	23668 KB	Output is correct
32	Correct	59 ms	23756 KB	Output is correct
33	Correct	618 ms	185448 KB	Output is correct
34	Correct	594 ms	185296 KB	Output is correct
35	Correct	661 ms	185384 KB	Output is correct
36	Correct	730 ms	184520 KB	Output is correct
37	Correct	676 ms	184424 KB	Output is correct
38	Correct	703 ms	184576 KB	Output is correct
39	Correct	2889 ms	184828 KB	Output is correct
40	Correct	2982 ms	185076 KB	Output is correct
41	Correct	2942 ms	184960 KB	Output is correct
42	Correct	549 ms	184224 KB	Output is correct
43	Correct	636 ms	184552 KB	Output is correct
44	Correct	629 ms	184520 KB	Output is correct
45	Correct	678 ms	184680 KB	Output is correct
46	Correct	684 ms	184508 KB	Output is correct
47	Correct	643 ms	184556 KB	Output is correct
48	Correct	619 ms	184584 KB	Output is correct
49	Correct	578 ms	184808 KB	Output is correct
50	Correct	626 ms	184616 KB	Output is correct

Subtask #6

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	384 KB	Output is correct
2	Correct	3 ms	384 KB	Output is correct
3	Correct	3 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Correct	3 ms	640 KB	Output is correct
7	Correct	7 ms	640 KB	Output is correct
8	Correct	4 ms	640 KB	Output is correct
9	Correct	3 ms	640 KB	Output is correct
10	Correct	3 ms	640 KB	Output is correct
11	Correct	3 ms	640 KB	Output is correct
12	Correct	4 ms	640 KB	Output is correct
13	Correct	3 ms	640 KB	Output is correct
14	Correct	3 ms	640 KB	Output is correct
15	Correct	3 ms	640 KB	Output is correct
16	Correct	8 ms	2688 KB	Output is correct
17	Correct	6 ms	2688 KB	Output is correct
18	Correct	8 ms	2688 KB	Output is correct
19	Correct	35 ms	12156 KB	Output is correct
20	Correct	29 ms	12072 KB	Output is correct
21	Correct	33 ms	12072 KB	Output is correct
22	Correct	31 ms	12152 KB	Output is correct
23	Correct	31 ms	12032 KB	Output is correct
24	Correct	29 ms	12032 KB	Output is correct
25	Correct	30 ms	12032 KB	Output is correct
26	Correct	31 ms	12152 KB	Output is correct
27	Execution timed out	3043 ms	503024 KB	Time limit exceeded
28	Halted	0 ms	0 KB	-