#include <bits/stdc++.h>
using namespace std;
struct circle {
int x, y, r;
};
int n;
vector<pair<circle, int>> v;
const bool operator>(const pair<circle, int> &lhs, const pair<circle, int> &rhs) {
if (lhs.first.r != rhs.first.r) return lhs.first.r > rhs.first.r;
return lhs.second < rhs.second;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
//priority_queue<pair<circle, int>> pq;
for (int i = 0; i < n; i++) {
int x, y, r;
cin >> x >> y >> r;
//pq.push({{x, y, r}, i});
v.push_back({{x, y, r}, i});
}
sort(v.begin(), v.end(), [](const pair<circle, int>& a, const pair<circle, int>& b) {
if (a.first.r != b.first.r) return a.first.r > b.first.r;
return a.second < b.second;
});
#ifdef DEBUG
//for (auto& c : v) {
// cout << c.first.x << ' ' << c.first.y << ' ' << c.first.r << ' ' << c.second << '\n';
//}
#endif
int idx = 0;
bitset<5005> used;
vector<int> ans(n);
while (idx < n) {
if (used[idx]) {
idx++;
continue;
}
used[idx] = true;
ans[v[idx].second] = v[idx].second;
for (int i = 0; i < n; i++) {
if (i == idx) continue;
if (hypot(v[i].first.x - v[idx].first.x, v[i].first.y - v[idx].first.y) <= v[i].first.r + v[idx].first.r) {
used[i] = true;
ans[v[i].second] = v[idx].second;
}
}
idx++;
}
/*bitset<5005> used;
vector<int> ans(n);
while (!pq.empty()) {
auto cur = pq.top(); pq.pop();
}*/
for (int i = 0; i < n; i++) {
if (i) cout << ' ';
cout << ans[i] + 1;
}
cout << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
356 KB |
Output is correct |
3 |
Correct |
2 ms |
432 KB |
Output is correct |
4 |
Correct |
3 ms |
448 KB |
Output is correct |
5 |
Correct |
2 ms |
496 KB |
Output is correct |
6 |
Correct |
2 ms |
632 KB |
Output is correct |
7 |
Correct |
2 ms |
632 KB |
Output is correct |
8 |
Incorrect |
2 ms |
632 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
157 ms |
12664 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
12664 KB |
Output is correct |
2 |
Runtime error |
1180 ms |
12664 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1287 ms |
12664 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
356 KB |
Output is correct |
3 |
Correct |
2 ms |
432 KB |
Output is correct |
4 |
Correct |
3 ms |
448 KB |
Output is correct |
5 |
Correct |
2 ms |
496 KB |
Output is correct |
6 |
Correct |
2 ms |
632 KB |
Output is correct |
7 |
Correct |
2 ms |
632 KB |
Output is correct |
8 |
Incorrect |
2 ms |
632 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
356 KB |
Output is correct |
3 |
Correct |
2 ms |
432 KB |
Output is correct |
4 |
Correct |
3 ms |
448 KB |
Output is correct |
5 |
Correct |
2 ms |
496 KB |
Output is correct |
6 |
Correct |
2 ms |
632 KB |
Output is correct |
7 |
Correct |
2 ms |
632 KB |
Output is correct |
8 |
Incorrect |
2 ms |
632 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |