Submission #978262

#	Time	Username	Problem	Language	Result	Execution time	Memory
978262		Halym2007	Circle selection (APIO18_circle_selection)	C++17	7 / 100	3062 ms	20052 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
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 ("input.txt", "r", stdin);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i].x >> a[i].y >> a[i].r;
		a[i].idx = i;
	}
	sort (a + 1, a + n + 1, cmp);
//	for (int i = 1; i <= n; ++i) {
//		cykar(a[i]);
//	}
//	cout << "\n\n";
	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;
			}
		}
	}
	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