/** vaziat sorati ghermeze **/
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define Mp make_pair
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;
ll pw(ll a , ll b, ll M) { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }
int n, id[N], ord[N], mark[N], Ans[N];
ll X[N], Y[N], R[N];
vector < ll > cm, Vec;
set < pii > seg[N << 2];
bool cmp(int i, int j) { return R[i] > R[j]; }
inline int lwr(ll x) { return lower_bound(all(cm), x) - cm.begin(); }
bool cross(int i, int j)
{
ll fir = (X[i] - X[j]) * (X[i] - X[j]) + (Y[i] - Y[j]) * (Y[i] - Y[j]);
ll sec = R[i] * R[i] + R[j] * R[j] + 2 * R[i] * R[j];
return sec >= fir;
}
void upd(pii x, int p, int v = 1, int tl = 0, int tr = SZ(cm))
{
if(p > tr || p < tl) return;
seg[v].insert(x);
if(tl == tr) return;
int mid = (tl + tr) >> 1;
upd(x, p, v << 1, tl, mid);
upd(x, p, v << 1 | 1, mid + 1, tr);
}
void get(int l, int r, int v = 1, int tl = 0, int tr = SZ(cm))
{
if(l > tr || r < tl || l > r) return;
if(l <= tl && tr <= r)
{
Vec.push_back(v);
return;
}
int mid = (tl + tr) >> 1;
get(l, r, v << 1, tl, mid);
get(l, r, v << 1 | 1, mid + 1, tr);
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
{
scanf("%lld%lld%lld", &X[i], &Y[i], &R[i]);
cm.push_back(X[i]);
ord[i] = i;
}
sort(ord + 1, ord + n + 1, cmp);
/*for(int i = 1; i <= n; i ++)
{
printf("%d ", ord[i]);
}
printf("\n");*/
sort(all(cm));
cm.resize(unique(all(cm)) - cm.begin());
for(int i = 1; i <= n; i ++)
{
id[i] = lwr(X[i]);
upd(Mp(Y[i], i), id[i]);
}
for(int i = 1; i <= n; i ++)
{
int I = ord[i];
if(Ans[I]) continue;
ll l = lwr(X[I] - 2 * R[I]), r = lwr(X[I] + 2 * R[I]), d = Y[I] - 2 * R[I], up = Y[I] + 2 * R[I];
Vec.clear();
get(l, r);
for(auto now : Vec)
{
pii last = Mp(d, -1);
while(1)
{
auto it = seg[now].upper_bound(last);
if(it == seg[now].end()) break;
last = *it;
if(Ans[it->S])
{
seg[now].erase(it);
continue;
}
if(it->F <= up)
{
///printf("checking %d and %d\n", I, it->S);
if(cross(it->S, I))
{
///printf("cross %d and %d\n", I, it->S);
Ans[it->S] = I;
seg[now].erase(it);
}
else
{
continue;
}
}
else
{
break;
}
}
}
}
for(int i = 1; i <= n; i ++)
{
printf("%d ", Ans[i]);
}
return 0;
}
/** test corner cases(n = 1?) watch for overflow or minus indices **/
Compilation message
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
71 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
circle_selection.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
74 | scanf("%lld%lld%lld", &X[i], &Y[i], &R[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
107 ms |
188096 KB |
Output is correct |
2 |
Correct |
102 ms |
188112 KB |
Output is correct |
3 |
Correct |
113 ms |
188252 KB |
Output is correct |
4 |
Correct |
106 ms |
188156 KB |
Output is correct |
5 |
Correct |
106 ms |
188212 KB |
Output is correct |
6 |
Correct |
102 ms |
188168 KB |
Output is correct |
7 |
Correct |
106 ms |
188228 KB |
Output is correct |
8 |
Correct |
107 ms |
188240 KB |
Output is correct |
9 |
Correct |
103 ms |
188148 KB |
Output is correct |
10 |
Correct |
104 ms |
188172 KB |
Output is correct |
11 |
Correct |
107 ms |
188164 KB |
Output is correct |
12 |
Correct |
103 ms |
188156 KB |
Output is correct |
13 |
Correct |
106 ms |
188228 KB |
Output is correct |
14 |
Correct |
102 ms |
188128 KB |
Output is correct |
15 |
Correct |
110 ms |
188192 KB |
Output is correct |
16 |
Correct |
106 ms |
188740 KB |
Output is correct |
17 |
Correct |
106 ms |
188880 KB |
Output is correct |
18 |
Correct |
106 ms |
188740 KB |
Output is correct |
19 |
Correct |
124 ms |
191676 KB |
Output is correct |
20 |
Correct |
124 ms |
191664 KB |
Output is correct |
21 |
Correct |
125 ms |
191672 KB |
Output is correct |
22 |
Correct |
128 ms |
191620 KB |
Output is correct |
23 |
Correct |
129 ms |
191616 KB |
Output is correct |
24 |
Correct |
126 ms |
191664 KB |
Output is correct |
25 |
Correct |
129 ms |
191664 KB |
Output is correct |
26 |
Correct |
125 ms |
191608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3108 ms |
405520 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
120 ms |
188144 KB |
Output is correct |
2 |
Correct |
1659 ms |
278904 KB |
Output is correct |
3 |
Execution timed out |
3098 ms |
402332 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3083 ms |
398996 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
107 ms |
188096 KB |
Output is correct |
2 |
Correct |
102 ms |
188112 KB |
Output is correct |
3 |
Correct |
113 ms |
188252 KB |
Output is correct |
4 |
Correct |
106 ms |
188156 KB |
Output is correct |
5 |
Correct |
106 ms |
188212 KB |
Output is correct |
6 |
Correct |
102 ms |
188168 KB |
Output is correct |
7 |
Correct |
106 ms |
188228 KB |
Output is correct |
8 |
Correct |
107 ms |
188240 KB |
Output is correct |
9 |
Correct |
103 ms |
188148 KB |
Output is correct |
10 |
Correct |
104 ms |
188172 KB |
Output is correct |
11 |
Correct |
107 ms |
188164 KB |
Output is correct |
12 |
Correct |
103 ms |
188156 KB |
Output is correct |
13 |
Correct |
106 ms |
188228 KB |
Output is correct |
14 |
Correct |
102 ms |
188128 KB |
Output is correct |
15 |
Correct |
110 ms |
188192 KB |
Output is correct |
16 |
Correct |
106 ms |
188740 KB |
Output is correct |
17 |
Correct |
106 ms |
188880 KB |
Output is correct |
18 |
Correct |
106 ms |
188740 KB |
Output is correct |
19 |
Correct |
124 ms |
191676 KB |
Output is correct |
20 |
Correct |
124 ms |
191664 KB |
Output is correct |
21 |
Correct |
125 ms |
191672 KB |
Output is correct |
22 |
Correct |
128 ms |
191620 KB |
Output is correct |
23 |
Correct |
129 ms |
191616 KB |
Output is correct |
24 |
Correct |
126 ms |
191664 KB |
Output is correct |
25 |
Correct |
129 ms |
191664 KB |
Output is correct |
26 |
Correct |
125 ms |
191608 KB |
Output is correct |
27 |
Correct |
159 ms |
195656 KB |
Output is correct |
28 |
Correct |
159 ms |
195652 KB |
Output is correct |
29 |
Correct |
164 ms |
195612 KB |
Output is correct |
30 |
Correct |
164 ms |
195652 KB |
Output is correct |
31 |
Correct |
161 ms |
195652 KB |
Output is correct |
32 |
Correct |
171 ms |
195676 KB |
Output is correct |
33 |
Correct |
1471 ms |
279300 KB |
Output is correct |
34 |
Correct |
1393 ms |
279384 KB |
Output is correct |
35 |
Correct |
1468 ms |
279092 KB |
Output is correct |
36 |
Correct |
1648 ms |
278756 KB |
Output is correct |
37 |
Correct |
1538 ms |
278748 KB |
Output is correct |
38 |
Correct |
1583 ms |
278844 KB |
Output is correct |
39 |
Incorrect |
2469 ms |
243636 KB |
Output isn't correct |
40 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
107 ms |
188096 KB |
Output is correct |
2 |
Correct |
102 ms |
188112 KB |
Output is correct |
3 |
Correct |
113 ms |
188252 KB |
Output is correct |
4 |
Correct |
106 ms |
188156 KB |
Output is correct |
5 |
Correct |
106 ms |
188212 KB |
Output is correct |
6 |
Correct |
102 ms |
188168 KB |
Output is correct |
7 |
Correct |
106 ms |
188228 KB |
Output is correct |
8 |
Correct |
107 ms |
188240 KB |
Output is correct |
9 |
Correct |
103 ms |
188148 KB |
Output is correct |
10 |
Correct |
104 ms |
188172 KB |
Output is correct |
11 |
Correct |
107 ms |
188164 KB |
Output is correct |
12 |
Correct |
103 ms |
188156 KB |
Output is correct |
13 |
Correct |
106 ms |
188228 KB |
Output is correct |
14 |
Correct |
102 ms |
188128 KB |
Output is correct |
15 |
Correct |
110 ms |
188192 KB |
Output is correct |
16 |
Correct |
106 ms |
188740 KB |
Output is correct |
17 |
Correct |
106 ms |
188880 KB |
Output is correct |
18 |
Correct |
106 ms |
188740 KB |
Output is correct |
19 |
Correct |
124 ms |
191676 KB |
Output is correct |
20 |
Correct |
124 ms |
191664 KB |
Output is correct |
21 |
Correct |
125 ms |
191672 KB |
Output is correct |
22 |
Correct |
128 ms |
191620 KB |
Output is correct |
23 |
Correct |
129 ms |
191616 KB |
Output is correct |
24 |
Correct |
126 ms |
191664 KB |
Output is correct |
25 |
Correct |
129 ms |
191664 KB |
Output is correct |
26 |
Correct |
125 ms |
191608 KB |
Output is correct |
27 |
Execution timed out |
3108 ms |
405520 KB |
Time limit exceeded |
28 |
Halted |
0 ms |
0 KB |
- |