This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*input
11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define REP(i,j,k) for(int i = j ; i < k ; ++i)
#define RREP(i,j,k) for(int i = j ; i >=k ; --i)
#define A first
#define B second
#define mp make_pair
#define pb emplace_back
#define PII pair<int , int>
#define MEM(i,j) memset(i , j , sizeof i)
#define ALL(i) i.begin() , i.end()
#define DBGG(i,j) cout << i << " " << j << endl
#define DB4(i,j,k,l) cout << i << " " << j << " " << k << " " << l << endl
#define IOS cin.tie(0) , cout.sync_with_stdio(0)
#define endl "\n"
///------------------------------------------------------------
#define MAX 300090
#define getchar getchar_unlocked
#define INF 2e9
gp_hash_table<int_fast64_t , int> cc;
vector<PII> v[MAX];
vector<int> las;
int_fast64_t R = 1e14;
int n , pos;
int x[MAX] , y[MAX] , r[MAX] , sol[MAX] , ans[MAX];
inline int_fast64_t trs(int a , int b){ return 1LL * a * 1000000009 + b; }
inline int cmp(int a , int b){ return mp(r[a] , -a) > mp(r[b] , -b); }
inline int tch(int a , int b){
int_fast64_t val = 1LL * (x[a] - x[b]) * (x[a] - x[b]) + 1LL * (y[a] - y[b]) * (y[a] - y[b]);
return (val <= 1LL * (r[a] + r[b]) * (r[a] + r[b]));
}
inline int rit(){
int val = 0 , f = 1;
char c = getchar();
while(!isdigit(c)){
if(c == '-') f = -1;
c = getchar();
}
while(isdigit(c)){
val = (val << 1) + (val << 3) + (c & 15);
c = getchar();
}
return val * f;
}
int32_t main(){
n = rit();
REP(i , 1 , n + 1) x[i] = rit() , y[i] = rit() , r[i] = rit();
// REP(i , 1 , n + 1) cin >> x[i] >> y[i] >> r[i];
REP(i , 1 , n + 1) sol[i] = i;
sort(sol + 1 , sol + 1 + n , cmp);
// REP(idx , 1 , n + 1){ int i = sol[idx];
// if(ans[i]) continue;
// REP(j , 1 , n + 1) if(ans[j] == 0 && tch(i , j)) ans[j] = i;
// }
REP(i , 1 , n + 1) las.pb(i);
int del = 1000000;
REP(idx , 1 , n + 1){ int i = sol[idx];
if(ans[i]) continue;
// DBGG("solve = " , i);
if(R / 5 > r[i] && del > 1000){
del = 0;
cc.clear();
R = r[sol[1]];
vector<int> nw;
for(auto j : las){
if(ans[j]) continue;
nw.pb(j);
int xx = x[j] / R , yy = y[j] / R;
if(cc.find(trs(xx , yy)) == cc.end()){
v[pos].clear();
v[pos].pb(0 , 1);
cc[trs(xx , yy)] = pos ++;
if(pos == MAX) pos = 0;
}
v[cc[trs(xx , yy)]].pb(j , v[cc[trs(xx , yy)]].size() + 1);
}
swap(nw , las);
}
int xx = x[i] / R , yy = y[i] / R;
REP(ii , xx - 2 , xx + 3) REP(jj , yy - 2 , yy + 3){
if(cc.find(trs(ii , jj)) != cc.end()){
int id = cc[trs(ii , jj)] , pre = 0;
while(v[id][pre].B < v[id].size()){
int now = v[id][pre].B;
if(tch(i , v[id][now].A)){
ans[v[id][now].A] = i;
del ++;
v[id][pre].B = v[id][now].B;
}
else pre = now;
}
// for(auto to : v[id]){
// if(ans[to.A] == 0 && tch(i , to.A)) ans[to.A] = i;
// }
}
}
}
REP(i , 1 , n + 1) printf("%d " , ans[i]);
puts("");
return 0;
}
// 7 2 7 4 5 6 7 7 4 7 6
Compilation message (stderr)
circle_selection.cpp: In function 'int32_t main()':
circle_selection.cpp:102:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(v[id][pre].B < v[id].size()){
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |