Submission #103206

#	Time	Username	Problem	Language	Result	Execution time	Memory
103206		E869120	Circle selection (APIO18_circle_selection)	C++14	30 / 100	3096 ms	815568 KiB

circle_selection

#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 (stderr)

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 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 23 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13