#include<bits/stdc++.h>
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define sz(x) (int)(x).size()
typedef long long ll;
typedef long double ld;
using namespace std;
//const int N = (int)3e5 + 10;
//struct seg{
// int a[4*N];
// int p[4*N];
// void clr(int x){
// fill(a , a + 4 * N , x);
// fill(p , p + 4 * N , x);
// }
// void push(int v){
//
// }
// int get(int v , int tl , int tr , int l , int r){
// if(tl == l && tr == r){
// return a[v];
// }
// int mid = (tl + tr) >> 1 , v1 = v << 1;
// push(v);
//
// }
//};
#define int long long
vector < array < int , 3 > > c;
bool intersec(int i , int j){
if(1ll * (c[i][2] + c[j][2]) * (c[i][2] + c[j][2]) >= 1ll * (c[i][0]-c[j][0])*(c[i][0]-c[j][0])
+ 1ll * (c[i][1]-c[j][1])*(c[i][1]-c[j][1])){
return true;
}
return false;
}
signed main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
c.resize(n);
for(auto &i : c)
cin >> i[0] >> i[1] >> i[2];
vector < int > p(n);
iota(all(p) , 0);
sort(all(p) , [&](int i , int j){
if(c[i][2] == c[j][2]){
return i < j;
}
return c[i][2] > c[j][2];
});
vector < int > ans(n, -1);
for(int i = 0 ; i < n; ++i){
int bst = -1;
for(int j = 0 ; j < i; ++j){
if(ans[p[j]] == -1 && intersec(p[i], p[j])){
bst = p[j];
break;
}
}
ans[p[i]] = bst;
}
for(int i = 0; i < n; ++i){
if(ans[i] == -1){
cout << i + 1 << ' ';
}else
cout << ans[i] + 1 << ' ';
}
return 0;
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10
2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7
1 1 1
100000000 1 1 1
1
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
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
320 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
4 ms |
588 KB |
Output is correct |
20 |
Correct |
2 ms |
588 KB |
Output is correct |
21 |
Correct |
3 ms |
588 KB |
Output is correct |
22 |
Correct |
43 ms |
640 KB |
Output is correct |
23 |
Correct |
42 ms |
588 KB |
Output is correct |
24 |
Correct |
46 ms |
628 KB |
Output is correct |
25 |
Correct |
42 ms |
588 KB |
Output is correct |
26 |
Correct |
42 ms |
588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1120 ms |
14108 KB |
Output is correct |
2 |
Correct |
872 ms |
20816 KB |
Output is correct |
3 |
Correct |
2009 ms |
20500 KB |
Output is correct |
4 |
Correct |
733 ms |
20844 KB |
Output is correct |
5 |
Execution timed out |
3093 ms |
16684 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Execution timed out |
3058 ms |
4164 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3076 ms |
11972 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
320 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
4 ms |
588 KB |
Output is correct |
20 |
Correct |
2 ms |
588 KB |
Output is correct |
21 |
Correct |
3 ms |
588 KB |
Output is correct |
22 |
Correct |
43 ms |
640 KB |
Output is correct |
23 |
Correct |
42 ms |
588 KB |
Output is correct |
24 |
Correct |
46 ms |
628 KB |
Output is correct |
25 |
Correct |
42 ms |
588 KB |
Output is correct |
26 |
Correct |
42 ms |
588 KB |
Output is correct |
27 |
Correct |
5 ms |
972 KB |
Output is correct |
28 |
Correct |
5 ms |
972 KB |
Output is correct |
29 |
Correct |
5 ms |
972 KB |
Output is correct |
30 |
Correct |
166 ms |
976 KB |
Output is correct |
31 |
Correct |
186 ms |
972 KB |
Output is correct |
32 |
Correct |
176 ms |
972 KB |
Output is correct |
33 |
Correct |
45 ms |
7900 KB |
Output is correct |
34 |
Correct |
59 ms |
7808 KB |
Output is correct |
35 |
Correct |
377 ms |
7748 KB |
Output is correct |
36 |
Execution timed out |
3073 ms |
6744 KB |
Time limit exceeded |
37 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
320 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
4 ms |
588 KB |
Output is correct |
20 |
Correct |
2 ms |
588 KB |
Output is correct |
21 |
Correct |
3 ms |
588 KB |
Output is correct |
22 |
Correct |
43 ms |
640 KB |
Output is correct |
23 |
Correct |
42 ms |
588 KB |
Output is correct |
24 |
Correct |
46 ms |
628 KB |
Output is correct |
25 |
Correct |
42 ms |
588 KB |
Output is correct |
26 |
Correct |
42 ms |
588 KB |
Output is correct |
27 |
Correct |
1120 ms |
14108 KB |
Output is correct |
28 |
Correct |
872 ms |
20816 KB |
Output is correct |
29 |
Correct |
2009 ms |
20500 KB |
Output is correct |
30 |
Correct |
733 ms |
20844 KB |
Output is correct |
31 |
Execution timed out |
3093 ms |
16684 KB |
Time limit exceeded |
32 |
Halted |
0 ms |
0 KB |
- |