#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, ll> 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)) ); }
string st1() {
sort(A,A+n, [] (pi x, pi y) { if(x.f!=y.f) return x.f > y.f; else return x.s < y.s; } );
FOR(ii,0,n) {
ll i = A[ii].s;
ll r = A[ii].f;
if(done[i]) continue;
ans[i] = i;
FOR(j,ii+1,n) {
if(!done[A[j].s] && mdist(C[i].f,C[i].s,C[A[j].s].f,C[A[j].s].s) <= (ld)r + (ld)A[j].f) {
done[A[j].s] = 1;
ans[A[j].s] = i;
}
}
}
FOR(i,0,n) cout << ans[i] + 1 << ' '; cout << '\n';
string s = ""; FOR(i,0,n) s += to_string(ans[i]+1); return s;
}
string st2() {
sort(A,A+n, [] (pi x, pi y) { if(x.f!=y.f) return x.f > y.f; else return x.s < y.s; } );
mmst(ans,0);
multiset <pi> ms_smol,ms_big; // x-coord, radius, index
FOR(i,0,n) {
ms_smol.ins(pi(C[A[i].s].f+A[i].f, i));
ms_big.ins(pi(C[A[i].s].f-A[i].f, i));
}
FOR(i,0,n) {
if(ms_smol.find(pi(C[A[i].s].f+A[i].f, i)) == ms_smol.end()) { continue; }
while(1) {
auto itrrr = ms_big.find(pi(C[A[i].s].f-A[i].f, i));
auto itr2 = next(itrrr);
if(itr2==ms_big.end()) break;
if(C[A[i].s].f + A[i].f >= itr2->f) { ans[A[itr2->s].s] = A[i].s; ms_smol.erase(ms_smol.find(pi(C[A[itr2->s].s].f+A[itr2->s].f, itr2->s))); ms_big.erase(itr2); }
else break;
}
while(1) {
auto itrrr = ms_smol.find(pi(C[A[i].s].f+A[i].f, i)); if(itrrr==ms_smol.begin()) break;
auto itr2 = prev(itrrr);
if(C[A[i].s].f - A[i].f <= itr2->f) { ans[A[itr2->s].s] = A[i].s; ms_smol.erase(itr2); ms_big.erase(ms_big.find(pi(C[A[itr2->s].s].f-A[itr2->s].f, itr2->s))); }
else break;
}
ms_smol.erase(ms_smol.find(pi(C[A[i].s].f+A[i].f,i)));
ms_big.erase(ms_big.find(pi(C[A[i].s].f-A[i].f,i)));
ans[A[i].s] = A[i].s;
}
FOR(i,0,n) cout << ans[i]+1 << ' '; cout << '\n';
string s = ""; FOR(i,0,n) s += to_string(ans[i]+1); return s;
}
// ll mdist(ll a, ll b, ll c, ll d) { return llabs(a-c)+llabs(b-d); }
void st3() {
vector<ll>inter(n,0); vector<bool>re(n,0); set <pi> ms;
vector <pi> events;
FOR(i,0,n) events.pb(pi(C[i].s-A[i].f,i)), events.pb(pi(C[i].s+A[i].f,-i-1));
sort(all(events), [] (pi x, pi y) { if(x.f != y.f) return x.f < y.f; else return x.s > y.s; } );
for(auto j : events) {
ll i = j.s;
if(i>=0) { ll r = A[i].f; ll x = C[i].f;
bool in = 1; pi near = pi(LLINF, LLINF);
if(!ms.empty()) {
// pi near = LLINF;
auto itr = ms.lower_bound(pi(x,0));
if(itr != ms.end()) near = min(near, pi(mdist(C[itr->s].f,C[itr->s].s, C[i].f, C[i].s)-(ld)A[itr->s].f, itr->s));
if(itr != ms.begin()) { --itr; near = min(near, pi(mdist(C[itr->s].f,C[itr->s].s, C[i].f, C[i].s)-(ld)A[itr->s].f, itr->s)); }
assert(near.f != LLINF);
if(near.f-EPS <= (ld)r) in = 0;
}
if(in) {
ms.ins(pi(x,i)); re[i] = 1;
} else {
re[i] = 0; assert(re[near.s]);
assert((ms.find(pi(C[near.s].f, near.s))!=ms.end()));
// assert(ms.find(pi(C[near.s].f+A[near.s].f, near.s))!=ms.end());
ms.erase(ms.find(pi(C[near.s].f, near.s)));
// ms.erase(ms.find(pi(C[near.s].f+A[near.s].f, near.s)));
re[near.s] = 0;
inter[i] = near.s;
inter[near.s] = i;
}
} else {
i = -i-1; if(re[i] == 0) continue;
ll r = A[i].f; ll x = C[i].f;
ms.erase(ms.find(pi(x,i)));
// bool in = 1; pi near = pi(LLINF, LLINF);
// if(!ms.empty()) {
// // pi near = LLINF;
// auto itr = ms.lower_bound(pi(x,0));
// if(itr != ms.end()) near = min(near, pi(mdist(C[itr->s].f,C[itr->s].s, C[i].f, C[i].s)-(ld)A[itr->s].f, itr->s));
// if(itr != ms.begin()) { --itr; near = min(near, pi(mdist(C[itr->s].f,C[itr->s].s, C[i].f, C[i].s)-(ld)A[itr->s].f, itr->s)); }
// assert(near.f != LLINF);
// if(near.f-EPS <= (ld)r) in = 0;
// }
// if(!in) {
// re[i] = 0; assert(re[near.s]);
// assert((ms.find(pi(C[near.s].f, near.s))!=ms.end()));
// // assert(ms.find(pi(C[near.s].f+A[near.s].f, near.s))!=ms.end());
// ms.erase(ms.find(pi(C[near.s].f, near.s)));
// // ms.erase(ms.find(pi(C[near.s].f+A[near.s].f, near.s)));
// re[near.s] = 0;
// inter[i] = near.s;
// inter[near.s] = i;
// }
auto itr = ms.lower_bound(pi(x,0));
if(itr != ms.end()) assert(itr->f > x);
if(itr != ms.begin() && itr != ms.end()) {
ll a = prev(itr)->s, b = itr->s;
if(mdist(C[a].f,C[a].s,C[b].f,C[b].s) <= (ld)A[a].f + (ld)A[b].f){
re[a] = re[b] = 0;
inter[a] = b;
inter[b] = a;
itr=ms.erase(prev(itr));
ms.erase(itr);
}
}
}
}
FOR(i,0,n) ans[i] = i;
FOR(i,0,n) if(!re[i]&&(A[inter[i]].f>A[i].f||(A[inter[i]].f==A[i].f&&inter[i]<i))) { ans[i] = inter[i]; }
FOR(i,0,n) cout << ans[i]+1 << ' '; cout<<'\n';
}
vector<pi>in;
bool s4 = 1; ll R = -1;
ll magic = 5; // odd number pls
bool 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 <ll, int> mp;
vector <ll> d;
set<pi>ind[MAXN];
void split() {
mp.clear();
FOR(i,0,siz(d)+1) ind[i].clear();
d.clear();
R /= 2;
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]].ins(pi(C[i].s, i));
return;
}
void 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]].ins(pi(C[i].s,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;
ind[x].erase(ind[x].find(pi(y,i)));
ll ii = i;
FOR(i,x-magic/2,x+magic/2+1) {
if(i <= 0 || i > siz(d) )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();) {
if(inter(ii,j->s)) { j=ind[i].erase(j); }
else ++j;
}
}
}
FOR(i,0,n) assert(done[i]);
FOR(i,0,n) cout << ans[i] + 1 << ' ';
}
int main()
{
// freopen("int","r",stdin); freopen("out","w",stdout);
FAST
cin >> n;
FOR(i,0,n) {
cin >> C[i].f >> C[i].s >> A[i].f; if(0)in.pb(pi(C[i].f,A[i].f));
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(st1() != st2()) {
// cerr << n << '\n';
// for(auto i : in) cerr << i.f << ' ' << i.s << '\n';
// assert(0);
// }
// assert(st1() == st2());
if(n <= 5000&&0) {
st1();
} else if(s2&&0) {
st2();
} else if(s4||1) { // becos i edited editorial solution here (the AC solution)
st4();
}else {
st3();
}
}
// 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: In function 'std::__cxx11::string st1()':
circle_selection.cpp:19:25: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
#define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ++ii)
^
circle_selection.cpp:55:2: note: in expansion of macro 'FOR'
FOR(i,0,n) cout << ans[i] + 1 << ' '; cout << '\n';
^~~
circle_selection.cpp:55:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
FOR(i,0,n) cout << ans[i] + 1 << ' '; cout << '\n';
^~~~
circle_selection.cpp: In function 'std::__cxx11::string st2()':
circle_selection.cpp:19:25: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
#define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ++ii)
^
circle_selection.cpp:85:2: note: in expansion of macro 'FOR'
FOR(i,0,n) cout << ans[i]+1 << ' '; cout << '\n';
^~~
circle_selection.cpp:85:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
FOR(i,0,n) cout << ans[i]+1 << ' '; cout << '\n';
^~~~
circle_selection.cpp: In function 'void st3()':
circle_selection.cpp:120:7: warning: unused variable 'r' [-Wunused-variable]
ll r = A[i].f; ll x = C[i].f;
^
circle_selection.cpp:19:25: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
#define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ++ii)
^
circle_selection.cpp:157:2: note: in expansion of macro 'FOR'
FOR(i,0,n) cout << ans[i]+1 << ' '; cout<<'\n';
^~~
circle_selection.cpp:157:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
FOR(i,0,n) cout << ans[i]+1 << ' '; cout<<'\n';
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
14464 KB |
Output is correct |
| 2 |
Incorrect |
17 ms |
14464 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
593 ms |
39332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
14320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1712 ms |
42448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
14464 KB |
Output is correct |
| 2 |
Incorrect |
17 ms |
14464 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
14464 KB |
Output is correct |
| 2 |
Incorrect |
17 ms |
14464 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
