#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = int;
using pll = pair<ll, ll>;
template <class T>
using vec = vector<T>;
template <class T>
using indexed_set =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define FOR(i, s, e) for (ll i = (ll)s; i < e; i++)
#define CFOR(i, s, e) for (ll i = (ll)s; i <= e; i++)
#define TRAV(e, a) for (const auto &e : a)
#define all(x) x.begin(), x.end()
#define dbg(x) cerr << "ln" << __LINE__ << ": " << #x << " = " << x << endl;
template <class T, class = decay_t<decltype(*begin(declval<T>()))>,
class = enable_if_t<!is_same<T, string>::value>>
ostream &operator<<(ostream &out, const T &obj) {
out << "[";
for (auto it = obj.begin(); it != obj.end(); it++) {
out << &", "[2 * (it == obj.begin())] << *it;
}
return out << "]";
}
template <class K, class V>
ostream &operator<<(ostream &out, const pair<K, V> &obj) {
return out << "(" << obj.first << ", " << obj.second << ")";
}
struct circle {
ll x, y, r, id;
};
ostream &operator<<(ostream &out, const circle &obj) {
return out << vec<ll>{obj.x, obj.y, obj.r, obj.id};
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n;
cin >> n;
vec<circle> a(n);
FOR(i, 0, n) {
cin >> a[i].x >> a[i].y >> a[i].r;
a[i].id = i;
}
vec<bool> visited(n);
vec<ll> ans(n);
sort(all(a), [&](const circle &o1, const circle &o2) {
return (o1.r == o2.r) ? o1.id < o2.id : o1.r > o2.r;
});
FOR(i, 0, n) {
if (visited[a[i].id]) continue;
ans[a[i].id] = a[i].id;
visited[a[i].id] = 1;
FOR(j, i + 1, n) {
if (visited[a[j].id]) continue;
if (pow(a[i].x - a[j].x, 2) + pow(a[i].y - a[j].y, 2) <=
pow(a[i].r + a[j].r, 2)) {
visited[a[j].id] = 1;
ans[a[j].id] = a[i].id;
}
}
}
FOR(i, 0, n) cout << ans[i] + 1 << " ";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
2 ms |
604 KB |
Output is correct |
20 |
Correct |
2 ms |
604 KB |
Output is correct |
21 |
Correct |
2 ms |
604 KB |
Output is correct |
22 |
Correct |
28 ms |
604 KB |
Output is correct |
23 |
Correct |
27 ms |
600 KB |
Output is correct |
24 |
Correct |
27 ms |
604 KB |
Output is correct |
25 |
Correct |
27 ms |
604 KB |
Output is correct |
26 |
Correct |
28 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
109 ms |
15108 KB |
Output is correct |
2 |
Correct |
106 ms |
14996 KB |
Output is correct |
3 |
Correct |
107 ms |
14856 KB |
Output is correct |
4 |
Correct |
102 ms |
15188 KB |
Output is correct |
5 |
Execution timed out |
3022 ms |
10952 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Execution timed out |
3016 ms |
4968 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3014 ms |
14088 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
2 ms |
604 KB |
Output is correct |
20 |
Correct |
2 ms |
604 KB |
Output is correct |
21 |
Correct |
2 ms |
604 KB |
Output is correct |
22 |
Correct |
28 ms |
604 KB |
Output is correct |
23 |
Correct |
27 ms |
600 KB |
Output is correct |
24 |
Correct |
27 ms |
604 KB |
Output is correct |
25 |
Correct |
27 ms |
604 KB |
Output is correct |
26 |
Correct |
28 ms |
604 KB |
Output is correct |
27 |
Correct |
5 ms |
860 KB |
Output is correct |
28 |
Correct |
5 ms |
860 KB |
Output is correct |
29 |
Correct |
4 ms |
860 KB |
Output is correct |
30 |
Correct |
107 ms |
912 KB |
Output is correct |
31 |
Correct |
103 ms |
860 KB |
Output is correct |
32 |
Correct |
104 ms |
912 KB |
Output is correct |
33 |
Correct |
38 ms |
6100 KB |
Output is correct |
34 |
Correct |
40 ms |
5972 KB |
Output is correct |
35 |
Correct |
38 ms |
5976 KB |
Output is correct |
36 |
Execution timed out |
3031 ms |
4952 KB |
Time limit exceeded |
37 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
2 ms |
604 KB |
Output is correct |
20 |
Correct |
2 ms |
604 KB |
Output is correct |
21 |
Correct |
2 ms |
604 KB |
Output is correct |
22 |
Correct |
28 ms |
604 KB |
Output is correct |
23 |
Correct |
27 ms |
600 KB |
Output is correct |
24 |
Correct |
27 ms |
604 KB |
Output is correct |
25 |
Correct |
27 ms |
604 KB |
Output is correct |
26 |
Correct |
28 ms |
604 KB |
Output is correct |
27 |
Correct |
109 ms |
15108 KB |
Output is correct |
28 |
Correct |
106 ms |
14996 KB |
Output is correct |
29 |
Correct |
107 ms |
14856 KB |
Output is correct |
30 |
Correct |
102 ms |
15188 KB |
Output is correct |
31 |
Execution timed out |
3022 ms |
10952 KB |
Time limit exceeded |
32 |
Halted |
0 ms |
0 KB |
- |