#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";
long long dist = (1LL * ((long long)x[i] - x[j]) * ((long long)x[i] - x[j]) + 1LL * ((long long)y[i] - y[j]) * ((long long)y[i] - y[j]));
long long rd = 1LL * ((long long)r[i] + r[j]) * ((long long)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 '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;
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
7380 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
467 ms |
34588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
359 ms |
22132 KB |
Output is correct |
| 3 |
Correct |
1484 ms |
59516 KB |
Output is correct |
| 4 |
Correct |
1479 ms |
59576 KB |
Output is correct |
| 5 |
Correct |
1295 ms |
52820 KB |
Output is correct |
| 6 |
Correct |
569 ms |
32052 KB |
Output is correct |
| 7 |
Correct |
302 ms |
20520 KB |
Output is correct |
| 8 |
Correct |
56 ms |
10476 KB |
Output is correct |
| 9 |
Correct |
1501 ms |
59316 KB |
Output is correct |
| 10 |
Correct |
1235 ms |
50208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1338 ms |
59932 KB |
Output is correct |
| 2 |
Correct |
147 ms |
26924 KB |
Output is correct |
| 3 |
Correct |
888 ms |
42424 KB |
Output is correct |
| 4 |
Correct |
1881 ms |
73404 KB |
Output is correct |
| 5 |
Correct |
2131 ms |
81788 KB |
Output is correct |
| 6 |
Correct |
952 ms |
42800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
7380 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
7380 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
