#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
#define pb push_back
#define ins insert
#define f first
#define s second
#define db 0
#define EPS (1e-7) //0.0000001 the value
#define PI (acos(-1))
#define MAXN (300006)
#define MAXK 26
#define MAXX 15000006
#define ll long long int
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ++ii)
#define space " "
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define ph push
#define btinpct(x) __builtin_popcountll(x)
#define p2(x) (1LL<<(x))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <ll, int> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
ll n; bool s2 = 1;
pi A[MAXN], C[MAXN];
bool done[MAXN];
int ans[MAXN];
#define sq(x) ((x)*(x))
ld sqr(ll x) { return (x ? sqrtl(x) : 0); }
ld mdist(ll a, ll b, ll c, ll d) { return sqr( sq(llabs(a-c)) + sq(llabs(b-d)) ); }
vector<pi>in;
bool s4 = 1; ll R = -1;
#define sdb __attribute((optimize("-Ofast"), target("arch=sandybridge")))
ll magic = 5; // odd number pls
inline bool sdb inter(ll i, ll j) {
if(done[j]) return 1;
if(mdist(C[i].f, C[i].s, C[j].f, C[j].s) <= (ld)A[i].f + (ld) A[j].f) {
// assert(i < j);
done[j] = 1;
ans[j] = i;
return 1;
}
else return 0;
}
unordered_map <int, int> mp;
vector <int> d;
vector<pi>ind[MAXN],tmp[MAXN];
int latest = 0;
void sdb split() {
FOR(i,0,latest+1) tmp[i].clear();
ll new_R = R/2; // if(new_R%2)new_R++;
ll co = 1;
mp.clear();
FOR(i,1,latest+1) {
if(ind[i].empty()) { assert(0); continue; } assert(co < MAXN);
if(ind[i].size()==1) { if(mp[C[ind[i][0].s].f/new_R] == 0) mp[C[ind[i][0].s].f/new_R] = co++; tmp[mp[C[ind[i][0].s].f/new_R]].pb(ind[i][0]); }
else {
ll one = LLINF;
ll two = 0;
for(auto j : ind[i]) two = max(two, C[j.s].f/new_R);
for(auto j : ind[i]) one = min(one, C[j.s].f/new_R);
ll three = -LLINF;
for(auto j : ind[i]) three = ((C[j.s].f/new_R) != one && (C[j.s].f/new_R) != two) ? C[j.s].f/new_R : three;
// if(three != -LLINF) {
// for(auto j : ind[i]) {
// cer
// ll cmp = C[j.s].f/new_R;
// if(one == cmp || two == cmp || three == cmp);
// else {
// cout << "BRUHHH\n";
// exit(0);
// }
// }
// }
// cerr << "1,2,3: " << one << ' ' << two << ' ' << three << '\n';
if(one == two) { // 1
assert(three==-LLINF);
if(mp[one]==0)mp[one] = co ++;
} else if(three == -LLINF) { // 2
if(mp[one]==0)mp[one] = co ++;
if(mp[two]==0)mp[two] = co++;
} else { // 3
swap(two,three);
if(mp[one]==0)mp[one] = co ++;
if(mp[two]==0)mp[two] = co ++;
if(mp[three]==0)mp[three] = co ++;
}
assert(co+3 < MAXN);
for(auto j : ind[i]) {
// cerr << C[j.s].f << ' ' << new_R << ' ' << C[j.s].f/new_R << ' ' << C[j.s].f/R << '\n';
tmp[mp[C[j.s].f/new_R]].pb(j);
}
// cerr << '\n' << '\n';
}
}
R=new_R; latest = co-1;
assert(co < MAXN);
FOR(i,0,latest+1) ind[i]=tmp[i];
// ll p = -LLINF;
// FOR(i,1,latest+1) {
// assert(ind[i].size());
// ll hmm = C[ind[i][0].s].f/R;
// for(auto j : ind[i]) if(hmm != C[j.s].f/R) assert(0);
// assert(hmm >= p);
// p = hmm;
// }
}
void sdb st4() {
FOR(i,0,n) {
d.pb(C[i].f/R);
}
sort(all(d)); d.resize(unique(all(d))-d.begin());
ll co = 1; for(auto i : d) mp[i] = co++;
FOR(i,0,n) {
ind[mp[C[i].f/R]].pb(pi(C[i].s,i));
latest = max(latest, mp[C[i].f/R]);
}
// FOR(i,1,latest+1) sort(all(ind[i]));
int p[n+5];
for(ll i=0;i<n;i++) p[i]=i;
sort(p,p+n,[](ll x, ll y){if(A[x].f==A[y].f)return A[x].s<A[y].s; else return A[x].f>A[y].f;});
// assert(ind[0].empty());
FOR(iii,0,n) {
ll i = p[iii]; // cerr << i+1 << ' ';
if(done[i]) continue;
done[i] = 1;
ans[i] = i; if(A[i].f < R/2) { split(); }
ll x = mp[C[i].f/R], y = C[i].s;
ll ii = i;
FOR(i,x-magic/2,x+magic/2+1) {
if(i <= 0||i>latest)continue;
// ll d = llabs(x-i) * R + R;
// auto lower = ind[i].lower_bound(pi(sqr((4ll*sq(R))-sq(d))-y, 0));
// auto upper = (ind[i].upper_bound(pi(sqr((4ll*sq(R))-sq(d))+y, LLINF)));
// if(upper != ind[i].end() && pi(lower->f,lower->s) > pi(upper->f,upper->s)) continue;
// if(lower == ind[i].end()) continue;
for(auto j = ind[i].begin(); j != ind[i].end();j++) {
if(inter(ii,j->s)) {}
}
}
}
FOR(i,0,n) assert(done[i]);
FOR(i,0,n) cout << ans[i] + 1 << ' ';
}
inline ll ri() {
ll x = 0;
char ch = getchar_unlocked();
while (ch < '0' || ch > '9') ch = getchar_unlocked();
while (ch >= '0' && ch <= '9'){
x = (x << 3ll) + (x << 1ll) + ch - '0';
ch = getchar_unlocked();
}
return x;
}
int sdb main()
{
// freopen("int","r",stdin); // freopen("out","w",stdout);
FAST
//cin >> n;
n=ri();
FOR(i,0,n) {
C[i].f=ri();C[i].s=ri();A[i].f=ri();// cin >> C[i].f >> C[i].s >> A[i].f; if(0)in.pb(pi(C[i].f,A[i].f));
C[i].f+=1e9;
if(C[i].s) s2 = 0;
A[i].s = i;
if(R == -1) R = A[i].f;
if(R != A[i].f) s4 = 0;
R=max(R,A[i].f);
} // if(R%2)R++;
// if(st1() != st2()) {
// cerr << n << '\n';
// for(auto i : in) cerr << i.f << ' ' << i.s << '\n';
// assert(0);
// }
// assert(st1() == st2());
st4();
}
// 1 10 1 4 5 6 7 8 4 10 6
// 1 2 1 4 5 6 7 8 4 2 6
/*
3
5 0 3
10 0 2
20 0 8
4
1 0 3
10 0 5
15 0 1
20 0 10
8
1 4
14 12
6 10
0 6
14 0
9 6
3 2
0 0
*
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
*/
Compilation message
circle_selection.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization ("Ofast")
circle_selection.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization ("unroll-loops")
circle_selection.cpp: In function 'void st4()':
circle_selection.cpp:143:24: warning: unused variable 'y' [-Wunused-variable]
ll x = mp[C[i].f/R], y = C[i].s;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
14464 KB |
Output is correct |
| 2 |
Correct |
19 ms |
14464 KB |
Output is correct |
| 3 |
Correct |
17 ms |
14464 KB |
Output is correct |
| 4 |
Correct |
18 ms |
14464 KB |
Output is correct |
| 5 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 6 |
Correct |
16 ms |
14464 KB |
Output is correct |
| 7 |
Correct |
17 ms |
14464 KB |
Output is correct |
| 8 |
Incorrect |
16 ms |
14464 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
183 ms |
34536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1274 ms |
39384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
14464 KB |
Output is correct |
| 2 |
Correct |
19 ms |
14464 KB |
Output is correct |
| 3 |
Correct |
17 ms |
14464 KB |
Output is correct |
| 4 |
Correct |
18 ms |
14464 KB |
Output is correct |
| 5 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 6 |
Correct |
16 ms |
14464 KB |
Output is correct |
| 7 |
Correct |
17 ms |
14464 KB |
Output is correct |
| 8 |
Incorrect |
16 ms |
14464 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
14464 KB |
Output is correct |
| 2 |
Correct |
19 ms |
14464 KB |
Output is correct |
| 3 |
Correct |
17 ms |
14464 KB |
Output is correct |
| 4 |
Correct |
18 ms |
14464 KB |
Output is correct |
| 5 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 6 |
Correct |
16 ms |
14464 KB |
Output is correct |
| 7 |
Correct |
17 ms |
14464 KB |
Output is correct |
| 8 |
Incorrect |
16 ms |
14464 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
