Submission #49272

#	Time	Username	Problem	Language	Result	Execution time	Memory
49272		Noam527	Circle selection (APIO18_circle_selection)	C++17	100 / 100	2801 ms	241556 KiB

circle_selection

#include <bits/stdc++.h>
#define endl '\n'
#define flush fflush(stdout), cout.flush()
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define debug cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
#define yesno(X) cout << ((X) ? "YES" : "NO") << endl
#define noyes(X) cout << ((X) ? "NO" : "YES") << endl
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7, inf = 1e9 + 7;
const ll hs = 199;
const ldb eps = 1e-9, pi = acos(-1);
using namespace std;

const ll MAGIC = 2;

ll sqr(ll x) {
	return x * x;
}

struct circle {
	ll x, y, r, ind, ord;
	circle(int xx = 0, int yy = 0, int rr = 0, int ii = 0) {
		x = xx;
		y = yy;
		r = rr;
		ind = ii;
	}
	int intersect(const circle &a) const {
		if (sqr(x - a.x) + sqr(y - a.y) <= sqr(r + a.r)) return ord;
		return inf;
	}
	bool operator < (const circle &a) const {
		if (y != a.y) return y < a.y;
		return ind < a.ind;
	}
};

struct grid {
	vector<int> comp;
	vector<set<circle>> G;
	int maxr;
	grid(const vector<int> &sortedx, int R = 1) {
		maxr = R;
		comp.push_back(sortedx[0] / R);
		for (int i = 1; i < sortedx.size(); i++) {
			if (comp.back() < sortedx[i] / R)
				comp.push_back(sortedx[i] / R);
		}
		G.resize(comp.size());
	}
	int lowerbound(int x) {
		static int lo, hi, mid;
		lo = 0, hi = comp.size() - 1;
		while (lo < hi) {
			mid = (lo + hi) / 2;
			if (comp[mid] < x) lo = mid + 1;
			else hi = mid;
		}
		if (comp[lo] < x) lo++;
		return lo;
	}
	int find(const circle &a) {
		int X = a.x / maxr;
		int rtn = inf, best = inf;
		int i = lowerbound(X - MAGIC);
		set<circle>::iterator it;
		while (i < comp.size() && comp[i] <= X + MAGIC) {
			it = G[i].lower_bound(circle(0, a.y - MAGIC * maxr - 1, 0, 0));
			while (it != G[i].end() && abs(a.y - it->y) <= MAGIC * maxr + 1) {
//				cout << "found something" << endl;
//				cout << "iterator is " << it->x << " " << it->y << " " << it->r << endl;
//				cout << "while finding for " << a.x << " " << a.y << " " << a.r << endl;
				if (it->intersect(a) < best) {
					best = it->ord;
					rtn = it->ind;
				}
				it++;
			}
			i++;
		}
		return rtn;
	}
	void insert(const circle &a) {
		G[lowerbound(a.x / maxr)].insert(a);
	}
};

int n;
vector<circle> order;
vector<int> sortedx;
vector<grid> G;
int curR;
vector<int> ans;

bool ordcmp(const circle &a, const circle &b) {
	if (a.r != b.r) return a.r > b.r;
	return a.ind < b.ind;
}

int main() {
	fast;
	cin >> n;
	order.resize(n);
	sortedx.resize(n);
	ans.resize(n);
	for (int i = 0, p[3]; i < n; i++) {
		cin >> p[0] >> p[1] >> p[2];
		p[0] += 1e9, p[1] += 1e9;
		order[i] = circle(p[0], p[1], p[2], i);
		sortedx[i] = p[0];
	}
	sort(order.begin(), order.end(), ordcmp);
	for (int i = 0; i < n; i++) order[i].ord = i;
	sort(sortedx.begin(), sortedx.end());
	curR = order[0].r;
	G.push_back(grid(sortedx, curR));
	G[0].insert(order[0]);
	ans[order[0].ind] = order[0].ind;
	for (int i = 1, tmp; i < n; i++) {
		tmp = inf;
		for (int j = 0; tmp == inf && j < G.size(); j++) {
			tmp = G[j].find(order[i]);
		}
		if (tmp < inf) ans[order[i].ind] = tmp;
		else {
			ans[order[i].ind] = order[i].ind;
			if (2 * order[i].r <= curR) {
				curR = order[i].r;
				G.push_back(grid(sortedx, curR));
			}
			G.back().insert(order[i]);
		}
	}
	for (const auto &i : ans) cout << i + 1 << " "; cout << endl;
//	for (int i = 0; i < min(n, 10); i++) cout << order[i].ind << " "; cout << endl;
//	cout << order[0].intersect(order[1]) << endl;
}

Compilation message (stderr)

circle_selection.cpp: In constructor 'grid::grid(const std::vector<int>&, int)':
circle_selection.cpp:47:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i < sortedx.size(); i++) {
                   ~~^~~~~~~~~~~~~~~~
circle_selection.cpp: In member function 'int grid::find(const circle&)':
circle_selection.cpp:69:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (i < comp.size() && comp[i] <= X + MAGIC) {
          ~~^~~~~~~~~~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:123:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; tmp == inf && j < G.size(); j++) {
                                 ~~^~~~~~~~~~
circle_selection.cpp:136:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (const auto &i : ans) cout << i + 1 << " "; cout << endl;
  ^~~
circle_selection.cpp:136:50: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (const auto &i : ans) cout << i + 1 << " "; cout << endl;
                                                  ^~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 30 / 30
• Subtask 6: 13 / 13