#include <bits/stdc++.h>
#pragma GCC optimize("O0")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pi;
#define MAX 301010
#define MAXS 20
#define INF 1000000010
#define bb ' '
#define ln '\n'
#define Ln '\n'
pair<pi, pi> in[MAX];
int X[MAX];
int Y[MAX];
int R[MAX];
int ind[MAX];
int ri[MAX];
int ans[MAX];
inline ll sq(ll x) {
return x * x;
}
inline bool chk(int i, int j) {
return sq(X[i] - X[j]) + sq(Y[i] - Y[j]) <= sq(R[i] + R[j]);
}
bool isrange(int x, int y) {
if (x < 0 || y < 0) return false;
return true;
}
inline ll trans(int x, int y) {
return ((ll)x * (ll)INF) + y;
}
bool cmp(pair<pi, pi>& p1, pair<pi, pi>& p2) {
if (p1.first.first == p2.first.first) return p1.first.second < p2.first.second;
else return p1.first.first > p2.first.first;
}
unordered_map<ll, vector<int>> mp;
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int N;
cin >> N;
int i;
for (i = 1; i <= N; i++) cin >> in[i].second.first >> in[i].second.second >> in[i].first.first, in[i].first.second = i;
sort(in + 1, in + N + 1, cmp);
for (i = 1; i <= N; i++) tie(X[i], Y[i], R[i], ind[i]) = make_tuple(in[i].second.first + INF, in[i].second.second + INF, in[i].first.first, in[i].first.second);
int k;
int s, e;
e = 0;
for (k = 30; k >= 0; k--) {
int r = 1 << k;
s = e + 1;
if (R[s] < r / 2) continue;
mp.clear();
e = 0;
for (i = s; i <= N; i++) {
if (ans[i]) continue;
int x, y;
x = X[i] >> k;
y = Y[i] >> k;
if (R[i] < r / 2 && !e) e = i - 1;
int xx, yy;
mp[((ll)x << 31LL) + y].push_back(i);
}
if (e == 0) e = N;
for (i = s; i <= e; i++) {
if (ans[i]) continue;
ans[i] = i;
int x, y;
x = X[i] / r;
y = Y[i] / r;
int xx, yy;
for (xx = x - 2; xx <= x + 2; xx++) for (yy = y - 2; yy <= y + 2; yy++) {
ll t = ((ll)xx << 31LL) + yy;
vector<int> v;
for (auto c : mp[t]) {
if (hk(c, i)) ans[c] = i;
else
v.push_back(c);
}
mp[t] = v;
}
}
}
for (i = 1; i <= N; i++) ri[ind[i]] = i;
for (i = 1; i <= N; i++) cout << ind[ans[ri[i]]] << bb;
}
Compilation message
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:64:8: warning: unused variable 'xx' [-Wunused-variable]
64 | int xx, yy;
| ^~
circle_selection.cpp:64:12: warning: unused variable 'yy' [-Wunused-variable]
64 | int xx, yy;
| ^~
circle_selection.cpp:79:11: error: 'hk' was not declared in this scope; did you mean 'k'?
79 | if (hk(c, i)) ans[c] = i;
| ^~
| k
