Submission #1235583

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235583		Matthewwww	Circle selection (APIO18_circle_selection)	C++17	7 / 100	3094 ms	14292 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
#ifdef LOCAL
#define freopen(...) "i miss you"
#define err cerr
#else
#define err if (0) cerr
#endif

int d2 (pair<int, int> a, pair<int, int> b) {
	return (a.f-b.f)*(a.f-b.f)+(a.s-b.s)*(a.s-b.s);
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<pair<pair<int, int>, int>> vt(n);
	for (auto &i: vt) cin >> i.f.f >> i.f.s >> i.s;
	vector<int> ord(n);
	iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&](int a, int b) { if (vt[a].s-vt[b].s) return vt[a].s > vt[b].s; return a < b;});
	vector<int> ans(n, -1);
	for (int i: ord) if (!~ans[i])
		for (int j: ord) if (!~ans[j] && d2(vt[i].f, vt[j].f) <= (vt[i].s+vt[j].s)*(vt[i].s+vt[j].s))
			ans[j] = i;
	for (int i: ans) cout << i+1 << " ";
}

// no llama :(

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