Submission #932359

#	Time	Username	Problem	Language	Result	Execution time	Memory
932359		siewjh	Circle selection (APIO18_circle_selection)	C++17	7 / 100	254 ms	25196 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 5005;
int ans[MAXN];
ll xv[MAXN], yv[MAXN], rv[MAXN];
bool die[MAXN], cross[MAXN][MAXN];
ll sq(ll x){
	return x * x;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int nums; cin >> nums;
	for (int i = 0; i < nums; i++) cin >> xv[i] >> yv[i] >> rv[i];
	for (int i = 0; i < nums; i++){
		cross[i][i] = 1;
		for (int j = i + 1; j < nums; j++) cross[i][j] = cross[j][i] = ((sq(xv[i] - xv[j]) + sq(yv[i] - yv[j])) <= sq(rv[i] + rv[j]));
	}
	while (true){
		int ind = -1; ll sz = 0;
		for (int i = 0; i < nums; i++)
			if (!die[i] && rv[i] > sz){
				sz = rv[i];
				ind = i;
			}
		if (ind == -1) break;
		for (int i = 0; i < nums; i++)
			if (!die[i] && cross[i][ind]){
				ans[i] = ind + 1;
				die[i] = 1;
			}
	}
	for (int i = 0; i < nums; i++) cout << ans[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