oj.uz

Submission #103208

# Submission time Handle Problem Language Result Execution time Memory
103208 2019-03-29T08:37:29 Z E869120 Circle selection (APIO18_circle_selection) C++14
30 / 100
 3000 ms 1032692 KB 
#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<int> num;
};

Node vec[13000000];

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() {
	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:144: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:164:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &N);
  ~~~~~^~~~~~~~~~~~
circle_selection.cpp:166: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 446 ms 509148 KB Output is correct
2 Correct 456 ms 509176 KB Output is correct
3 Correct 496 ms 509176 KB Output is correct
4 Correct 490 ms 509180 KB Output is correct
5 Correct 530 ms 509316 KB Output is correct
6 Correct 476 ms 509304 KB Output is correct
7 Correct 479 ms 509304 KB Output is correct
8 Correct 480 ms 509272 KB Output is correct
9 Correct 465 ms 509308 KB Output is correct
10 Correct 483 ms 509244 KB Output is correct
11 Correct 466 ms 509432 KB Output is correct
12 Correct 496 ms 509312 KB Output is correct
13 Correct 437 ms 509176 KB Output is correct
14 Correct 450 ms 509280 KB Output is correct
15 Correct 515 ms 509320 KB Output is correct
16 Correct 465 ms 509328 KB Output is correct
17 Correct 462 ms 509376 KB Output is correct
18 Correct 473 ms 509180 KB Output is correct
19 Correct 484 ms 509696 KB Output is correct
20 Correct 543 ms 509708 KB Output is correct
21 Correct 513 ms 509688 KB Output is correct
22 Correct 509 ms 509776 KB Output is correct
23 Correct 474 ms 509608 KB Output is correct
24 Correct 468 ms 509640 KB Output is correct
25 Correct 521 ms 509724 KB Output is correct
26 Correct 491 ms 509584 KB Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 493 ms 509264 KB Output is correct
2 Correct 1293 ms 517192 KB Output is correct
3 Runtime error 1990 ms 1032692 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2326 ms 533524 KB Output is correct
2 Correct 2336 ms 533244 KB Output is correct
3 Correct 2426 ms 533328 KB Output is correct
4 Correct 2467 ms 533244 KB Output is correct
5 Correct 2307 ms 533328 KB Output is correct
6 Correct 2271 ms 533312 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 509148 KB Output is correct
2 Correct 456 ms 509176 KB Output is correct
3 Correct 496 ms 509176 KB Output is correct
4 Correct 490 ms 509180 KB Output is correct
5 Correct 530 ms 509316 KB Output is correct
6 Correct 476 ms 509304 KB Output is correct
7 Correct 479 ms 509304 KB Output is correct
8 Correct 480 ms 509272 KB Output is correct
9 Correct 465 ms 509308 KB Output is correct
10 Correct 483 ms 509244 KB Output is correct
11 Correct 466 ms 509432 KB Output is correct
12 Correct 496 ms 509312 KB Output is correct
13 Correct 437 ms 509176 KB Output is correct
14 Correct 450 ms 509280 KB Output is correct
15 Correct 515 ms 509320 KB Output is correct
16 Correct 465 ms 509328 KB Output is correct
17 Correct 462 ms 509376 KB Output is correct
18 Correct 473 ms 509180 KB Output is correct
19 Correct 484 ms 509696 KB Output is correct
20 Correct 543 ms 509708 KB Output is correct
21 Correct 513 ms 509688 KB Output is correct
22 Correct 509 ms 509776 KB Output is correct
23 Correct 474 ms 509608 KB Output is correct
24 Correct 468 ms 509640 KB Output is correct
25 Correct 521 ms 509724 KB Output is correct
26 Correct 491 ms 509584 KB Output is correct
27 Correct 519 ms 510356 KB Output is correct
28 Correct 532 ms 510308 KB Output is correct
29 Correct 514 ms 510452 KB Output is correct
30 Correct 499 ms 510324 KB Output is correct
31 Correct 544 ms 510260 KB Output is correct
32 Correct 521 ms 510196 KB Output is correct
33 Correct 1072 ms 518160 KB Output is correct
34 Correct 1086 ms 518232 KB Output is correct
35 Correct 1166 ms 518164 KB Output is correct
36 Correct 1102 ms 517348 KB Output is correct
37 Correct 1133 ms 517348 KB Output is correct
38 Correct 1166 ms 517224 KB Output is correct
39 Execution timed out 3048 ms 517720 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 509148 KB Output is correct
2 Correct 456 ms 509176 KB Output is correct
3 Correct 496 ms 509176 KB Output is correct
4 Correct 490 ms 509180 KB Output is correct
5 Correct 530 ms 509316 KB Output is correct
6 Correct 476 ms 509304 KB Output is correct
7 Correct 479 ms 509304 KB Output is correct
8 Correct 480 ms 509272 KB Output is correct
9 Correct 465 ms 509308 KB Output is correct
10 Correct 483 ms 509244 KB Output is correct
11 Correct 466 ms 509432 KB Output is correct
12 Correct 496 ms 509312 KB Output is correct
13 Correct 437 ms 509176 KB Output is correct
14 Correct 450 ms 509280 KB Output is correct
15 Correct 515 ms 509320 KB Output is correct
16 Correct 465 ms 509328 KB Output is correct
17 Correct 462 ms 509376 KB Output is correct
18 Correct 473 ms 509180 KB Output is correct
19 Correct 484 ms 509696 KB Output is correct
20 Correct 543 ms 509708 KB Output is correct
21 Correct 513 ms 509688 KB Output is correct
22 Correct 509 ms 509776 KB Output is correct
23 Correct 474 ms 509608 KB Output is correct
24 Correct 468 ms 509640 KB Output is correct
25 Correct 521 ms 509724 KB Output is correct
26 Correct 491 ms 509584 KB Output is correct
27 Execution timed out 3131 ms 536196 KB Time limit exceeded
28 Halted 0 ms 0 KB -