#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <iterator>
using namespace std;
struct cir
{
int x, y, r, i;
bool operator <(const cir &a) const
{
return r != a.r ? r > a.r : i < a.i;
}
};
cir arr[300010];
int num[300010];
int res[300010];
bool inter(const cir &a, const cir &b)
{
return 1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y) <= 1LL * (a.r + b.r) * (a.r + b.r);
}
int main()
{
//freopen("in", "r", stdin);
//freopen("out", "w", stdout);
int n, i, j;
scanf("%d", &n);
for(i = 1; i <= n; i++)
{
int x, y, r;
scanf("%d%d%d", &x, &y, &r);
arr[i] = { x, y, r, i };
}
sort(arr + 1, arr + n + 1);
if(n <= 5000)
{
for(i = 1; i <= n; i++)
if(!num[i])
for(j = 1; j <= n; j++)
if(!num[j] && inter(arr[i], arr[j]))
num[j] = arr[i].i;
for(i = 1; i <= n; i++)
res[arr[i].i] = num[i];
for(i = 1; i <= n; i++)
printf("%d ", res[i]);
return 0;
}
bool st2 = 1;
for(i = 1; i <= n; i++)
{
if(arr[i].y != 0)
{
st2 = 0;
break;
}
}
if(st2)
{
set<pair<int, int>> s;
for(i = 1; i <= n; i++)
{
s.insert({ arr[i].x - arr[i].r, i });
s.insert({ arr[i].x + arr[i].r, i });
}
for(i = 1; i <= n; i++)
{
if(num[i])
continue;
auto it = s.lower_bound({ arr[i].x - arr[i].r, -1 });
while(it != s.end() && it->first <= arr[i].x + arr[i].r)
{
int x = it->second;
if(!num[x])
num[x] = arr[i].i;
it++;
s.erase(prev(it));
}
}
for(i = 1; i <= n; i++)
res[arr[i].i] = num[i];
for(i = 1; i <= n; i++)
printf("%d ", res[i]);
return 0;
}
return 0;
}
Compilation message
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
circle_selection.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &x, &y, &r);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
484 KB |
Output is correct |
3 |
Correct |
2 ms |
500 KB |
Output is correct |
4 |
Correct |
2 ms |
524 KB |
Output is correct |
5 |
Correct |
2 ms |
600 KB |
Output is correct |
6 |
Correct |
2 ms |
696 KB |
Output is correct |
7 |
Correct |
2 ms |
696 KB |
Output is correct |
8 |
Correct |
2 ms |
696 KB |
Output is correct |
9 |
Correct |
3 ms |
696 KB |
Output is correct |
10 |
Correct |
3 ms |
696 KB |
Output is correct |
11 |
Correct |
2 ms |
696 KB |
Output is correct |
12 |
Correct |
2 ms |
696 KB |
Output is correct |
13 |
Correct |
2 ms |
696 KB |
Output is correct |
14 |
Correct |
2 ms |
696 KB |
Output is correct |
15 |
Correct |
3 ms |
696 KB |
Output is correct |
16 |
Correct |
3 ms |
696 KB |
Output is correct |
17 |
Correct |
3 ms |
696 KB |
Output is correct |
18 |
Correct |
3 ms |
696 KB |
Output is correct |
19 |
Correct |
5 ms |
724 KB |
Output is correct |
20 |
Correct |
5 ms |
724 KB |
Output is correct |
21 |
Correct |
6 ms |
736 KB |
Output is correct |
22 |
Correct |
44 ms |
752 KB |
Output is correct |
23 |
Correct |
47 ms |
812 KB |
Output is correct |
24 |
Correct |
44 ms |
828 KB |
Output is correct |
25 |
Correct |
54 ms |
828 KB |
Output is correct |
26 |
Correct |
45 ms |
828 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1141 ms |
37936 KB |
Output is correct |
2 |
Correct |
1065 ms |
38028 KB |
Output is correct |
3 |
Correct |
1156 ms |
38028 KB |
Output is correct |
4 |
Correct |
1210 ms |
38028 KB |
Output is correct |
5 |
Correct |
1092 ms |
38028 KB |
Output is correct |
6 |
Correct |
981 ms |
38028 KB |
Output is correct |
7 |
Correct |
958 ms |
38028 KB |
Output is correct |
8 |
Correct |
839 ms |
38028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
38028 KB |
Output is correct |
2 |
Incorrect |
63 ms |
38028 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
155 ms |
38028 KB |
Output isn't correct |
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 |
484 KB |
Output is correct |
3 |
Correct |
2 ms |
500 KB |
Output is correct |
4 |
Correct |
2 ms |
524 KB |
Output is correct |
5 |
Correct |
2 ms |
600 KB |
Output is correct |
6 |
Correct |
2 ms |
696 KB |
Output is correct |
7 |
Correct |
2 ms |
696 KB |
Output is correct |
8 |
Correct |
2 ms |
696 KB |
Output is correct |
9 |
Correct |
3 ms |
696 KB |
Output is correct |
10 |
Correct |
3 ms |
696 KB |
Output is correct |
11 |
Correct |
2 ms |
696 KB |
Output is correct |
12 |
Correct |
2 ms |
696 KB |
Output is correct |
13 |
Correct |
2 ms |
696 KB |
Output is correct |
14 |
Correct |
2 ms |
696 KB |
Output is correct |
15 |
Correct |
3 ms |
696 KB |
Output is correct |
16 |
Correct |
3 ms |
696 KB |
Output is correct |
17 |
Correct |
3 ms |
696 KB |
Output is correct |
18 |
Correct |
3 ms |
696 KB |
Output is correct |
19 |
Correct |
5 ms |
724 KB |
Output is correct |
20 |
Correct |
5 ms |
724 KB |
Output is correct |
21 |
Correct |
6 ms |
736 KB |
Output is correct |
22 |
Correct |
44 ms |
752 KB |
Output is correct |
23 |
Correct |
47 ms |
812 KB |
Output is correct |
24 |
Correct |
44 ms |
828 KB |
Output is correct |
25 |
Correct |
54 ms |
828 KB |
Output is correct |
26 |
Correct |
45 ms |
828 KB |
Output is correct |
27 |
Incorrect |
8 ms |
38028 KB |
Output isn't correct |
28 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
484 KB |
Output is correct |
3 |
Correct |
2 ms |
500 KB |
Output is correct |
4 |
Correct |
2 ms |
524 KB |
Output is correct |
5 |
Correct |
2 ms |
600 KB |
Output is correct |
6 |
Correct |
2 ms |
696 KB |
Output is correct |
7 |
Correct |
2 ms |
696 KB |
Output is correct |
8 |
Correct |
2 ms |
696 KB |
Output is correct |
9 |
Correct |
3 ms |
696 KB |
Output is correct |
10 |
Correct |
3 ms |
696 KB |
Output is correct |
11 |
Correct |
2 ms |
696 KB |
Output is correct |
12 |
Correct |
2 ms |
696 KB |
Output is correct |
13 |
Correct |
2 ms |
696 KB |
Output is correct |
14 |
Correct |
2 ms |
696 KB |
Output is correct |
15 |
Correct |
3 ms |
696 KB |
Output is correct |
16 |
Correct |
3 ms |
696 KB |
Output is correct |
17 |
Correct |
3 ms |
696 KB |
Output is correct |
18 |
Correct |
3 ms |
696 KB |
Output is correct |
19 |
Correct |
5 ms |
724 KB |
Output is correct |
20 |
Correct |
5 ms |
724 KB |
Output is correct |
21 |
Correct |
6 ms |
736 KB |
Output is correct |
22 |
Correct |
44 ms |
752 KB |
Output is correct |
23 |
Correct |
47 ms |
812 KB |
Output is correct |
24 |
Correct |
44 ms |
828 KB |
Output is correct |
25 |
Correct |
54 ms |
828 KB |
Output is correct |
26 |
Correct |
45 ms |
828 KB |
Output is correct |
27 |
Correct |
1141 ms |
37936 KB |
Output is correct |
28 |
Correct |
1065 ms |
38028 KB |
Output is correct |
29 |
Correct |
1156 ms |
38028 KB |
Output is correct |
30 |
Correct |
1210 ms |
38028 KB |
Output is correct |
31 |
Correct |
1092 ms |
38028 KB |
Output is correct |
32 |
Correct |
981 ms |
38028 KB |
Output is correct |
33 |
Correct |
958 ms |
38028 KB |
Output is correct |
34 |
Correct |
839 ms |
38028 KB |
Output is correct |
35 |
Correct |
2 ms |
38028 KB |
Output is correct |
36 |
Incorrect |
63 ms |
38028 KB |
Output isn't correct |
37 |
Halted |
0 ms |
0 KB |
- |