oj.uz

Submission #103207

# Submission time Handle Problem Language Result Execution time Memory
103207 2019-03-29T08:35:40 Z E869120 Circle selection (APIO18_circle_selection) C++14
30 / 100
 3000 ms 653860 KB 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#pragma warning (disable: 4996)

int cntv = 0;

struct Node {
	int val, l, r; vector<int> num;
};

Node vec[16000000];

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

	void init() {
		BASE.l = -1; BASE.r = -1; BASE.val = 0;
		vec[0] = BASE; 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 % 2 == 1) {
				int dep = i / 2;
				if (px >= (1LL << dep)) {
					if (vec[cx].r == -1) { vec[cx].r = size_; vec[size_] = BASE; size_++; }
					cx = vec[cx].r; px -= (1LL << dep);
				}
				else {
					if (vec[cx].l == -1) { vec[cx].l = size_; vec[size_] = BASE; size_++; }
					cx = vec[cx].l;
				}
			}
			else {
				int dep = i / 2;
				if (py >= (1LL << dep)) {
					if (vec[cx].r == -1) { vec[cx].r = size_; vec[size_] = BASE; size_++; }
					cx = vec[cx].r; py -= (1LL << dep);
				}
				else {
					if (vec[cx].l == -1) { vec[cx].l = size_; vec[size_] = BASE; size_++; }
					cx = vec[cx].l;
				}
			}
		}
		vec[cx].val++; vec[cx].num.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 % 2 == 1) {
				int dep = i / 2;
				if (px >= (1LL << dep)) {
					if (vec[cx].r == -1) { vec[cx].r = size_; vec[size_] = BASE; size_++; }
					cx = vec[cx].r; px -= (1LL << dep);
				}
				else {
					if (vec[cx].l == -1) { vec[cx].l = size_; vec[size_] = BASE; size_++; }
					cx = vec[cx].l;
				}
			}
			else {
				int dep = i / 2;
				if (py >= (1LL << dep)) {
					if (vec[cx].r == -1) { vec[cx].r = size_; vec[size_] = BASE; size_++; }
					cx = vec[cx].r; py -= (1LL << dep);
				}
				else {
					if (vec[cx].l == -1) { vec[cx].l = size_; vec[size_] = BASE; size_++; }
					cx = vec[cx].l;
				}
			}
		}
		vec[cx].val--; vec[cx].num.clear();
	}
	void query_(long long ax, long long ay, long long bx, long long 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 : vec[u].num) 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() {
	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() {
	scanf("%lld", &N);
	for (int i = 1; i <= N; i++) {
		//X[i] = Rand(); Y[i] = Rand(); R[i] = (1LL << 23);
		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:5:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
circle_selection.cpp: In function 'void solve_subtasks()':
circle_selection.cpp:143: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:162:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &N);
  ~~~~~^~~~~~~~~~~~
circle_selection.cpp:165: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 565 ms 626608 KB Output is correct
2 Correct 592 ms 626680 KB Output is correct
3 Correct 574 ms 626568 KB Output is correct
4 Correct 577 ms 626680 KB Output is correct
5 Correct 560 ms 626680 KB Output is correct
6 Correct 615 ms 626808 KB Output is correct
7 Correct 614 ms 626808 KB Output is correct
8 Correct 565 ms 626808 KB Output is correct
9 Correct 599 ms 626552 KB Output is correct
10 Correct 619 ms 626680 KB Output is correct
11 Correct 619 ms 626552 KB Output is correct
12 Correct 571 ms 626632 KB Output is correct
13 Correct 570 ms 626704 KB Output is correct
14 Correct 617 ms 626760 KB Output is correct
15 Correct 542 ms 626572 KB Output is correct
16 Correct 564 ms 626780 KB Output is correct
17 Correct 600 ms 626908 KB Output is correct
18 Correct 539 ms 626872 KB Output is correct
19 Correct 620 ms 627108 KB Output is correct
20 Correct 630 ms 627144 KB Output is correct
21 Correct 589 ms 627072 KB Output is correct
22 Correct 577 ms 627116 KB Output is correct
23 Correct 607 ms 627136 KB Output is correct
24 Correct 621 ms 627036 KB Output is correct
25 Correct 616 ms 627064 KB Output is correct
26 Correct 615 ms 627008 KB Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 626680 KB Output is correct
2 Correct 1257 ms 634728 KB Output is correct
3 Correct 3000 ms 650320 KB Output is correct
4 Execution timed out 3045 ms 650548 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2551 ms 650480 KB Output is correct
2 Correct 2537 ms 650520 KB Output is correct
3 Correct 2468 ms 650436 KB Output is correct
4 Correct 2370 ms 650660 KB Output is correct
5 Correct 2273 ms 650560 KB Output is correct
6 Correct 2323 ms 650536 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 565 ms 626608 KB Output is correct
2 Correct 592 ms 626680 KB Output is correct
3 Correct 574 ms 626568 KB Output is correct
4 Correct 577 ms 626680 KB Output is correct
5 Correct 560 ms 626680 KB Output is correct
6 Correct 615 ms 626808 KB Output is correct
7 Correct 614 ms 626808 KB Output is correct
8 Correct 565 ms 626808 KB Output is correct
9 Correct 599 ms 626552 KB Output is correct
10 Correct 619 ms 626680 KB Output is correct
11 Correct 619 ms 626552 KB Output is correct
12 Correct 571 ms 626632 KB Output is correct
13 Correct 570 ms 626704 KB Output is correct
14 Correct 617 ms 626760 KB Output is correct
15 Correct 542 ms 626572 KB Output is correct
16 Correct 564 ms 626780 KB Output is correct
17 Correct 600 ms 626908 KB Output is correct
18 Correct 539 ms 626872 KB Output is correct
19 Correct 620 ms 627108 KB Output is correct
20 Correct 630 ms 627144 KB Output is correct
21 Correct 589 ms 627072 KB Output is correct
22 Correct 577 ms 627116 KB Output is correct
23 Correct 607 ms 627136 KB Output is correct
24 Correct 621 ms 627036 KB Output is correct
25 Correct 616 ms 627064 KB Output is correct
26 Correct 615 ms 627008 KB Output is correct
27 Correct 637 ms 627516 KB Output is correct
28 Correct 641 ms 627648 KB Output is correct
29 Correct 627 ms 627600 KB Output is correct
30 Correct 617 ms 627452 KB Output is correct
31 Correct 643 ms 627572 KB Output is correct
32 Correct 667 ms 627416 KB Output is correct
33 Correct 1234 ms 635620 KB Output is correct
34 Correct 1189 ms 635572 KB Output is correct
35 Correct 1170 ms 635436 KB Output is correct
36 Correct 1214 ms 634596 KB Output is correct
37 Correct 1303 ms 634728 KB Output is correct
38 Correct 1370 ms 634556 KB Output is correct
39 Correct 2998 ms 635108 KB Output is correct
40 Execution timed out 3139 ms 634996 KB Time limit exceeded
41 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 565 ms 626608 KB Output is correct
2 Correct 592 ms 626680 KB Output is correct
3 Correct 574 ms 626568 KB Output is correct
4 Correct 577 ms 626680 KB Output is correct
5 Correct 560 ms 626680 KB Output is correct
6 Correct 615 ms 626808 KB Output is correct
7 Correct 614 ms 626808 KB Output is correct
8 Correct 565 ms 626808 KB Output is correct
9 Correct 599 ms 626552 KB Output is correct
10 Correct 619 ms 626680 KB Output is correct
11 Correct 619 ms 626552 KB Output is correct
12 Correct 571 ms 626632 KB Output is correct
13 Correct 570 ms 626704 KB Output is correct
14 Correct 617 ms 626760 KB Output is correct
15 Correct 542 ms 626572 KB Output is correct
16 Correct 564 ms 626780 KB Output is correct
17 Correct 600 ms 626908 KB Output is correct
18 Correct 539 ms 626872 KB Output is correct
19 Correct 620 ms 627108 KB Output is correct
20 Correct 630 ms 627144 KB Output is correct
21 Correct 589 ms 627072 KB Output is correct
22 Correct 577 ms 627116 KB Output is correct
23 Correct 607 ms 627136 KB Output is correct
24 Correct 621 ms 627036 KB Output is correct
25 Correct 616 ms 627064 KB Output is correct
26 Correct 615 ms 627008 KB Output is correct
27 Execution timed out 3125 ms 653860 KB Time limit exceeded
28 Halted 0 ms 0 KB -