oj.uz

답안 #103225

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
103225 2019-03-29T08:55:48 Z E869120 원 고르기 (APIO18_circle_selection) C++14
75 / 100
 3000 ms 503024 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<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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -