/** vaziat sorati ghermeze **/
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#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 = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;
int n, id[N], ord[N], Ans[N];
ll X[N], Y[N], R[N], base[N];
vector < ll > cm, Vec;
set < pll > 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(); }
inline bool cross(int i, int j)
{
return (base[i] + base[j] + 2 * (X[i] * X[j] + Y[i] * Y[j] + R[i] * R[j])) >= 0;
}
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;
base[i] = R[i] * R[i] - X[i] * X[i] - Y[i] * Y[i];
}
sort(ord + 1, ord + n + 1, cmp);
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:3: warning: ignoring #pragma comment [-Wunknown-pragmas]
3 | #pragma comment(linker, "/stack:200000000")
|
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
69 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
circle_selection.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
72 | scanf("%lld%lld%lld", &X[i], &Y[i], &R[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
19100 KB |
Output is correct |
2 |
Correct |
11 ms |
19100 KB |
Output is correct |
3 |
Correct |
11 ms |
19020 KB |
Output is correct |
4 |
Correct |
11 ms |
19020 KB |
Output is correct |
5 |
Correct |
11 ms |
19088 KB |
Output is correct |
6 |
Correct |
11 ms |
19104 KB |
Output is correct |
7 |
Correct |
11 ms |
19116 KB |
Output is correct |
8 |
Correct |
11 ms |
19148 KB |
Output is correct |
9 |
Correct |
11 ms |
19148 KB |
Output is correct |
10 |
Correct |
11 ms |
19148 KB |
Output is correct |
11 |
Correct |
11 ms |
19100 KB |
Output is correct |
12 |
Correct |
11 ms |
19148 KB |
Output is correct |
13 |
Correct |
11 ms |
19148 KB |
Output is correct |
14 |
Correct |
11 ms |
19096 KB |
Output is correct |
15 |
Correct |
11 ms |
19148 KB |
Output is correct |
16 |
Correct |
15 ms |
19892 KB |
Output is correct |
17 |
Correct |
14 ms |
19788 KB |
Output is correct |
18 |
Correct |
14 ms |
19788 KB |
Output is correct |
19 |
Correct |
44 ms |
23716 KB |
Output is correct |
20 |
Correct |
36 ms |
23716 KB |
Output is correct |
21 |
Correct |
37 ms |
23676 KB |
Output is correct |
22 |
Correct |
39 ms |
23572 KB |
Output is correct |
23 |
Correct |
50 ms |
23596 KB |
Output is correct |
24 |
Correct |
38 ms |
23680 KB |
Output is correct |
25 |
Correct |
38 ms |
23668 KB |
Output is correct |
26 |
Correct |
38 ms |
23676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
106 ms |
50608 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
19056 KB |
Output is correct |
2 |
Correct |
1578 ms |
135468 KB |
Output is correct |
3 |
Runtime error |
104 ms |
50588 KB |
Execution killed with signal 11 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
106 ms |
50564 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
19100 KB |
Output is correct |
2 |
Correct |
11 ms |
19100 KB |
Output is correct |
3 |
Correct |
11 ms |
19020 KB |
Output is correct |
4 |
Correct |
11 ms |
19020 KB |
Output is correct |
5 |
Correct |
11 ms |
19088 KB |
Output is correct |
6 |
Correct |
11 ms |
19104 KB |
Output is correct |
7 |
Correct |
11 ms |
19116 KB |
Output is correct |
8 |
Correct |
11 ms |
19148 KB |
Output is correct |
9 |
Correct |
11 ms |
19148 KB |
Output is correct |
10 |
Correct |
11 ms |
19148 KB |
Output is correct |
11 |
Correct |
11 ms |
19100 KB |
Output is correct |
12 |
Correct |
11 ms |
19148 KB |
Output is correct |
13 |
Correct |
11 ms |
19148 KB |
Output is correct |
14 |
Correct |
11 ms |
19096 KB |
Output is correct |
15 |
Correct |
11 ms |
19148 KB |
Output is correct |
16 |
Correct |
15 ms |
19892 KB |
Output is correct |
17 |
Correct |
14 ms |
19788 KB |
Output is correct |
18 |
Correct |
14 ms |
19788 KB |
Output is correct |
19 |
Correct |
44 ms |
23716 KB |
Output is correct |
20 |
Correct |
36 ms |
23716 KB |
Output is correct |
21 |
Correct |
37 ms |
23676 KB |
Output is correct |
22 |
Correct |
39 ms |
23572 KB |
Output is correct |
23 |
Correct |
50 ms |
23596 KB |
Output is correct |
24 |
Correct |
38 ms |
23680 KB |
Output is correct |
25 |
Correct |
38 ms |
23668 KB |
Output is correct |
26 |
Correct |
38 ms |
23676 KB |
Output is correct |
27 |
Correct |
73 ms |
28548 KB |
Output is correct |
28 |
Correct |
72 ms |
28576 KB |
Output is correct |
29 |
Correct |
85 ms |
28656 KB |
Output is correct |
30 |
Correct |
80 ms |
28628 KB |
Output is correct |
31 |
Correct |
72 ms |
28580 KB |
Output is correct |
32 |
Correct |
75 ms |
28544 KB |
Output is correct |
33 |
Correct |
1608 ms |
135468 KB |
Output is correct |
34 |
Correct |
1468 ms |
135468 KB |
Output is correct |
35 |
Correct |
1527 ms |
135876 KB |
Output is correct |
36 |
Correct |
1552 ms |
135948 KB |
Output is correct |
37 |
Correct |
1591 ms |
135988 KB |
Output is correct |
38 |
Correct |
1610 ms |
135956 KB |
Output is correct |
39 |
Incorrect |
2543 ms |
91124 KB |
Output isn't correct |
40 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
19100 KB |
Output is correct |
2 |
Correct |
11 ms |
19100 KB |
Output is correct |
3 |
Correct |
11 ms |
19020 KB |
Output is correct |
4 |
Correct |
11 ms |
19020 KB |
Output is correct |
5 |
Correct |
11 ms |
19088 KB |
Output is correct |
6 |
Correct |
11 ms |
19104 KB |
Output is correct |
7 |
Correct |
11 ms |
19116 KB |
Output is correct |
8 |
Correct |
11 ms |
19148 KB |
Output is correct |
9 |
Correct |
11 ms |
19148 KB |
Output is correct |
10 |
Correct |
11 ms |
19148 KB |
Output is correct |
11 |
Correct |
11 ms |
19100 KB |
Output is correct |
12 |
Correct |
11 ms |
19148 KB |
Output is correct |
13 |
Correct |
11 ms |
19148 KB |
Output is correct |
14 |
Correct |
11 ms |
19096 KB |
Output is correct |
15 |
Correct |
11 ms |
19148 KB |
Output is correct |
16 |
Correct |
15 ms |
19892 KB |
Output is correct |
17 |
Correct |
14 ms |
19788 KB |
Output is correct |
18 |
Correct |
14 ms |
19788 KB |
Output is correct |
19 |
Correct |
44 ms |
23716 KB |
Output is correct |
20 |
Correct |
36 ms |
23716 KB |
Output is correct |
21 |
Correct |
37 ms |
23676 KB |
Output is correct |
22 |
Correct |
39 ms |
23572 KB |
Output is correct |
23 |
Correct |
50 ms |
23596 KB |
Output is correct |
24 |
Correct |
38 ms |
23680 KB |
Output is correct |
25 |
Correct |
38 ms |
23668 KB |
Output is correct |
26 |
Correct |
38 ms |
23676 KB |
Output is correct |
27 |
Runtime error |
106 ms |
50608 KB |
Execution killed with signal 11 |
28 |
Halted |
0 ms |
0 KB |
- |