oj.uz

Submission #103206

# Submission time Handle Problem Language Result Execution time Memory
103206 2019-03-29T08:33:16 Z E869120 Circle selection (APIO18_circle_selection) C++14
30 / 100
 3000 ms 815568 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[20000000];

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 695 ms 783224 KB Output is correct
2 Correct 796 ms 783208 KB Output is correct
3 Correct 766 ms 783052 KB Output is correct
4 Correct 747 ms 783176 KB Output is correct
5 Correct 766 ms 783132 KB Output is correct
6 Correct 720 ms 783224 KB Output is correct
7 Correct 752 ms 783352 KB Output is correct
8 Correct 814 ms 783148 KB Output is correct
9 Correct 731 ms 783372 KB Output is correct
10 Correct 739 ms 783352 KB Output is correct
11 Correct 691 ms 783196 KB Output is correct
12 Correct 695 ms 783228 KB Output is correct
13 Correct 721 ms 783224 KB Output is correct
14 Correct 703 ms 783352 KB Output is correct
15 Correct 739 ms 783352 KB Output is correct
16 Correct 723 ms 783420 KB Output is correct
17 Correct 742 ms 783340 KB Output is correct
18 Correct 749 ms 783276 KB Output is correct
19 Correct 773 ms 783748 KB Output is correct
20 Correct 730 ms 783732 KB Output is correct
21 Correct 733 ms 783608 KB Output is correct
22 Correct 755 ms 783640 KB Output is correct
23 Correct 699 ms 783608 KB Output is correct
24 Correct 791 ms 783736 KB Output is correct
25 Correct 767 ms 783728 KB Output is correct
26 Correct 766 ms 783632 KB Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 741 ms 783232 KB Output is correct
2 Correct 1451 ms 791148 KB Output is correct
3 Correct 2966 ms 806992 KB Output is correct
4 Correct 2964 ms 815212 KB Output is correct
5 Correct 2861 ms 814544 KB Output is correct
6 Correct 1597 ms 799944 KB Output is correct
7 Correct 1146 ms 792012 KB Output is correct
8 Correct 763 ms 784984 KB Output is correct
9 Execution timed out 3081 ms 815312 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2666 ms 807244 KB Output is correct
2 Correct 2511 ms 814160 KB Output is correct
3 Correct 2728 ms 815404 KB Output is correct
4 Correct 2524 ms 814564 KB Output is correct
5 Correct 2565 ms 814792 KB Output is correct
6 Correct 2579 ms 815568 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 695 ms 783224 KB Output is correct
2 Correct 796 ms 783208 KB Output is correct
3 Correct 766 ms 783052 KB Output is correct
4 Correct 747 ms 783176 KB Output is correct
5 Correct 766 ms 783132 KB Output is correct
6 Correct 720 ms 783224 KB Output is correct
7 Correct 752 ms 783352 KB Output is correct
8 Correct 814 ms 783148 KB Output is correct
9 Correct 731 ms 783372 KB Output is correct
10 Correct 739 ms 783352 KB Output is correct
11 Correct 691 ms 783196 KB Output is correct
12 Correct 695 ms 783228 KB Output is correct
13 Correct 721 ms 783224 KB Output is correct
14 Correct 703 ms 783352 KB Output is correct
15 Correct 739 ms 783352 KB Output is correct
16 Correct 723 ms 783420 KB Output is correct
17 Correct 742 ms 783340 KB Output is correct
18 Correct 749 ms 783276 KB Output is correct
19 Correct 773 ms 783748 KB Output is correct
20 Correct 730 ms 783732 KB Output is correct
21 Correct 733 ms 783608 KB Output is correct
22 Correct 755 ms 783640 KB Output is correct
23 Correct 699 ms 783608 KB Output is correct
24 Correct 791 ms 783736 KB Output is correct
25 Correct 767 ms 783728 KB Output is correct
26 Correct 766 ms 783632 KB Output is correct
27 Correct 774 ms 784076 KB Output is correct
28 Correct 835 ms 784132 KB Output is correct
29 Correct 754 ms 784216 KB Output is correct
30 Correct 803 ms 783936 KB Output is correct
31 Correct 837 ms 783924 KB Output is correct
32 Correct 718 ms 784068 KB Output is correct
33 Correct 1316 ms 792108 KB Output is correct
34 Correct 1302 ms 792036 KB Output is correct
35 Correct 1337 ms 792132 KB Output is correct
36 Correct 1278 ms 791048 KB Output is correct
37 Correct 1336 ms 791140 KB Output is correct
38 Correct 1306 ms 791128 KB Output is correct
39 Execution timed out 3096 ms 791480 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 695 ms 783224 KB Output is correct
2 Correct 796 ms 783208 KB Output is correct
3 Correct 766 ms 783052 KB Output is correct
4 Correct 747 ms 783176 KB Output is correct
5 Correct 766 ms 783132 KB Output is correct
6 Correct 720 ms 783224 KB Output is correct
7 Correct 752 ms 783352 KB Output is correct
8 Correct 814 ms 783148 KB Output is correct
9 Correct 731 ms 783372 KB Output is correct
10 Correct 739 ms 783352 KB Output is correct
11 Correct 691 ms 783196 KB Output is correct
12 Correct 695 ms 783228 KB Output is correct
13 Correct 721 ms 783224 KB Output is correct
14 Correct 703 ms 783352 KB Output is correct
15 Correct 739 ms 783352 KB Output is correct
16 Correct 723 ms 783420 KB Output is correct
17 Correct 742 ms 783340 KB Output is correct
18 Correct 749 ms 783276 KB Output is correct
19 Correct 773 ms 783748 KB Output is correct
20 Correct 730 ms 783732 KB Output is correct
21 Correct 733 ms 783608 KB Output is correct
22 Correct 755 ms 783640 KB Output is correct
23 Correct 699 ms 783608 KB Output is correct
24 Correct 791 ms 783736 KB Output is correct
25 Correct 767 ms 783728 KB Output is correct
26 Correct 766 ms 783632 KB Output is correct
27 Execution timed out 3062 ms 810404 KB Time limit exceeded
28 Halted 0 ms 0 KB -