Submission #1173372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173372		Halym2007	Circle selection (APIO18_circle_selection)	C++17	7 / 100	3095 ms	8264 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
#define dur exit(0)
#define dur1 return(0)
const int N = 3e5 + 5;
int n, x[N], y[N], r[N], vis[N], jog[N];

int main () {
//	freopen ("input.txt", "r", stdin);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> x[i] >> y[i] >> r[i];
	}
	for (int i = 1; i <= n; ++i) {
		int x1 = -1;
		for (int j = 1; j <= n; ++j) {
			if (vis[j]) continue;
			if (~x1) {
				if (r[j] > r[x1]) {
					x1 = j;
				}
			}
			else {
				x1 = j;
			}
		}
		if (~x1) {
			vis[x1] = 1;
			jog[x1] = x1;
			for (int j = 1; j <= n; ++j) {
				if (vis[j]) continue;
				ll kk = abs (x[x1] - x[j]) * 1LL * abs (x[x1] - x[j]);
				ll kk1 = abs (y[x1] - y[j]) * 1LL * abs (y[x1] - y[j]);
				ll kk2 = r[x1] + r[j];
				if (kk1 + kk <= kk2 * kk2) {
					vis[j] = 1;
					jog[j] = x1;
				}
			}
		}
		else {
			assert (x1 == -1);
			break;
		}
	}
	for (int i = 1; i <= n; ++i) {
		cout << jog[i] << " ";
	}
	cout << "\n";
}
/*

11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1

*/

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