Submission #978445

#	Time	Username	Problem	Language	Result	Execution time	Memory
978445		Halym2007	Circle selection (APIO18_circle_selection)	C++17	7 / 100	269 ms	21852 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
#define ll long long
#define ff first
#define ss second
#define pii pair <int, int>
int n, jog[N];
bool vis[N];
struct coordinate {
	ll x, y, r, idx;
};
coordinate a[N];

bool intersect (coordinate x, coordinate y) {
	ll a1 = (x.x - y.x) * (x.x - y.x), a2 = (x.y - y.y) * (x.y - y.y), a3 = (x.r + y.r) * (x.r + y.r);
	return (a1 + a2 <= a3);
}

//void cykar (coordinate x) {
//	cout << x.x << " " << x.y << " " << x.r << " " << x.idx << "\n";
//}


bool cmp (coordinate x, coordinate y) {
	if (x.r > y.r) return 1;
	else if (x.r == y.r and x.idx < y.idx) return 1;
	return 0;
}


int main () {
//	freopen ("input1.txt", "r", stdin);
	cin >> n;
//	bool sub = 0;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i].x >> a[i].y >> a[i].r;
		a[i].idx = i;
//		if (a[i].y != 0) sub = 1;
	}
	sort (a + 1, a + n + 1, cmp);
	if (n <= 5000) {
		for (int i = 1; i <= n; ++i) {
			if (vis[i]) continue;
			jog[a[i].idx] = a[i].idx;	
			for (int j = i + 1; j <= n; ++j) {
				if (vis[j]) continue;
				if (intersect (a[i], a[j])) {
					jog[a[j].idx] = a[i].idx;
					vis[j] = 1;
				}
			}
		}
	}
	else {
		assert (n <= 5000);
		set <ll> s;
		map <ll, ll> val;
		for (int i = 1; i <= n; ++i) {
			ll l = a[i].x - a[i].r, r = a[i].x + a[i].r;
			if (i == 1) {
				s.insert (l);
				s.insert (r);
				val[l] = a[i].idx;
				val[r] = a[i].idx;
				
				jog[a[i].idx] = a[i].idx;
			}
			else {
				auto tr = s.lower_bound (l);
				if (tr != s.end()) {
					ll x = *tr;
					if (x <= r) {
						jog[a[i].idx] = val[x];
						continue;
					}
					else if (tr != s.begin()) {
						tr--;
						ll y = *tr;
						if (y <= l and r <= x) {
							jog[a[i].idx] = val[x];
							continue;
						}
					}
				}
				s.insert (l);
				s.insert (r);
				val[l] = a[i].idx;
				val[r] = a[i].idx;
				jog[a[i].idx] = a[i].idx;
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		cout << jog[i] << " ";
	}
}

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