#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define fi first
#define se second
#define pb push_back
//#define mp make_pair
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 3e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
int n, x[N], y[N], r[N];
int ans[N];
bool out[N];
unordered_map<int, int> mp;
vector<ii> vc[N];
bool ck(int i, int j){
// cout << i << " " << j << "\n";
ll dist = ((1LL * (x[i] - x[j]) * (x[i] - x[j]) + 1LL * (y[i] - y[j]) * (y[i] - y[j]));
ll rd = 1LL * (r[i] + r[j]) * (r[i] + r[j]);
return (dist <= rd);
}
void process(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> x[i] >> y[i] >> r[i];
set<ii> rem;
for(int i = 1; i <= n; i++) rem.insert({-r[i], i});
bool chk = 1;
for(int i = 1; i <= n; i++) chk &= (r[i] == 1);
if(chk){
for(int i = 1; i <= n; i++) cout << i << " ";
cout << "\n";
exit(0);
}
for(int i = 30; i >= 0; i--){// executing with radius (1LL << (i - 1)) to (1LL << i)
int rad = (1LL << i);
mp.clear();
for(int j = 1; j <= n; j++) vc[j].clear();
vector<int> diff;
for(int j = 1; j <= n; j++) if(!out[j]) diff.pb(x[j] / rad);
sort(diff.begin(), diff.end());
diff.resize(unique(diff.begin(), diff.end()) - diff.begin());
for(int j = 0; j < diff.size(); j++) mp[diff[j]] = j + 1;
for(int j = 1; j <= n; j++){
if(!out[j]){
//cout << "OK " << rad << " " << j << " " << x[j]/rad << " " << y[j] << "\n";
vc[mp[x[j]/rad]].pb({y[j], j});
}
}
for(int j = 1; j <= n; j++) sort(vc[j].begin(), vc[j].end());
while(!rem.empty() && -((*rem.begin()).fi) >= (1LL << (i - 1))){
int ind = (*rem.begin()).se;
// cout << rad << " " << ind << "\n";
assert(!out[ind]);
out[ind] = 1;
ans[ind] = ind;
rem.erase({-r[ind], ind});
for(int i2 = x[ind]/rad - 5; i2 <= x[ind]/rad + 5; i2++){
if(mp.find(i2) == mp.end()) continue;
int temp = mp[i2];
int le = (y[ind]/rad) - 5, ri = (y[ind] / rad) + 5;
// cout <<
le *= rad, ri *= rad;
// cout << le << " " << ri << "\n";
vector<ii>::iterator it = lower_bound(vc[temp].begin(), vc[temp].end(), make_pair(le, -oo));
for(; it != vc[temp].end(); it++){
if((*it).fi > ri) break;
if(out[(*it).se]) continue;
if(ck(ind, (*it).se)){
//cout << ind << " " << (*it).se << "\n";
ans[(*it).se] = ind;
rem.erase({-r[(*it).se], (*it).se});
out[(*it).se] = 1;
}
}
}
}
}
for(int i = 1; i <= n; i++) if(!ans[i]) ans[i] = i;
for(int i = 1; i <= n; i++) cout << ans[i] << " ";
cout << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
process();
}
Compilation message
circle_selection.cpp:16:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
16 | const int oo = 1e18 + 7, mod = 1e9 + 7;
| ~~~~~^~~
circle_selection.cpp: In function 'bool ck(int, int)':
circle_selection.cpp:29:2: error: 'll' was not declared in this scope
29 | ll dist = ((1LL * (x[i] - x[j]) * (x[i] - x[j]) + 1LL * (y[i] - y[j]) * (y[i] - y[j]));
| ^~
circle_selection.cpp:30:4: error: expected ';' before 'rd'
30 | ll rd = 1LL * (r[i] + r[j]) * (r[i] + r[j]);
| ^~~
| ;
circle_selection.cpp:31:10: error: 'dist' was not declared in this scope
31 | return (dist <= rd);
| ^~~~
circle_selection.cpp:31:18: error: 'rd' was not declared in this scope; did you mean 'r'?
31 | return (dist <= rd);
| ^~
| r
circle_selection.cpp: In function 'void process()':
circle_selection.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int j = 0; j < diff.size(); j++) mp[diff[j]] = j + 1;
| ~~^~~~~~~~~~~~~
