제출 #1173365

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1173365		Halym2007	원 고르기 (APIO18_circle_selection)	C++17	0 / 100	2874 ms	8368 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) {
		pii x1 = {-1, -1};
		for (int j = 1; j <= n; ++j) {
			if (vis[j]) continue;
			if (r[j] > x1.ff) {
				x1 = {r[j], j};
			}
		}
		if (~x1.ff) {
			vis[x1.ss] = 1;
			jog[x1.ss] = x1.ss;
			for (int j = 1; j <= n; ++j) {
				if (vis[j]) continue;
				ll kk = abs (x[x1.ss] - x[j]) * abs (x[x1.ss] - x[j]);
				ll kk1 = abs (y[x1.ss] - y[j]) * abs (y[x1.ss] - y[j]);
				ll kk2 = r[x1.ss] + r[j];
				if (ceil(sqrtl(kk1 + kk)) <= kk2) {
					vis[j] = 1;
					jog[j] = x1.ss;
				}
			}
		}
		else 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: 0 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13