#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
using namespace std;
const int maxn = 3e5 + 10;
typedef pair<int,int> ii;
typedef pair<ii,int> iii;
typedef pair<ii,ii> iiii;
#define ff first
#define ss second
inline int calc(ii x, ii y)
{
return (x.ff-y.ff)*(x.ff-y.ff) + (x.ss-y.ss)*(x.ss-y.ss);
}
bool dau[maxn];
int res[maxn];
int n,m;
iii a[maxn];
int id[maxn];
iiii hcn[maxn];
multiset<ii> f[8*maxn];
vector <int> tmp;
bool cmp(int x, int y)
{
if (a[x].ss!=a[y].ss) return a[x].ss>a[y].ss;
return x<y;
}
void update(int x, int lx, int rx, int idx, ii val)
{
// if (x==1)
// {
//// cout<<"+ "<<idx<<' '<<val.ff<<','<<val.ss<<'\n';
// }
f[x].insert(val);
if (lx==rx) return;
int mid=(lx+rx)/2;
if (idx<=mid) update(2*x,lx,mid,idx,val);
else update(2*x+1,mid+1,rx,idx,val);
}
void xoa(int x, int lx, int rx, int idx, ii val)
{
f[x].erase(f[x].find(val));
if (lx==rx) return;
int mid=(lx+rx)/2;
if (idx<=mid) xoa(2*x,lx,mid,idx,val);
else xoa(2*x+1,mid+1,rx,idx,val);
}
void qry(int x, int lx, int rx, int l, int r, int l2, int r2, int idx)
{
if (lx>r||rx<l) return;
if (lx>=l&&rx<=r)
{
ii temp = {l2,-1};
auto j = f[x].lower_bound(temp);
while (j!=f[x].end()&&(*j).ff <= r2)
{
// cerr<<l2<<" :: "<<r2<<" == "<<(*j).ff<<" , "<<(*j).ss<<endl;
int v = (*j).ss; j++;
if (!dau[v])
{
int val = calc(a[v].ff,a[idx].ff);
int val2 = (a[v].ss+a[idx].ss); val2*=val2;
if (val>val2) continue;
dau[v] = 1;
tmp.push_back(v);
}
}
return;
}
int mid=(lx+rx)/2;
qry(2*x,lx,mid,l,r,l2,r2,idx);
qry(2*x+1,mid+1,rx,l,r,l2,r2,idx);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin>>n;
map<int,int> mp;
for (int i=1; i<=n; i++)
{
cin>>a[i].ff.ff>>a[i].ff.ss>>a[i].ss;
hcn[i] = {{a[i].ff.ff-a[i].ss,a[i].ff.ss-a[i].ss},{a[i].ff.ff+a[i].ss,a[i].ff.ss + a[i].ss}};
mp[hcn[i].ff.ff] = 1;
mp[hcn[i].ss.ff] = 1;
dau[i]=0;
id[i]=i;
}
m=0;
for (auto &c:mp) c.ss = ++m;
for (int i=1; i<=n; i++)
{
hcn[i].ff.ff = mp[hcn[i].ff.ff];
hcn[i].ss.ff = mp[hcn[i].ss.ff];
// cerr<<i<<" := "<<hcn[i].ff.ff<<" - "<<hcn[i].ss.ff<<" : "<<hcn[i].ff.ss<<' '<<hcn[i].ss.ss<<endl;
update(1,1,m,hcn[i].ff.ff,{hcn[i].ff.ss,i});
update(1,1,m,hcn[i].ff.ff,{hcn[i].ss.ss,i});
update(1,1,m,hcn[i].ss.ff,{hcn[i].ff.ss,i});
update(1,1,m,hcn[i].ss.ff,{hcn[i].ss.ss,i});
}
sort(id+1,id+n+1,cmp);
for (int i=1; i<=n; i++)
{
int j=id[i];
if (dau[j]) continue;
tmp.clear();
qry(1,1,m,hcn[j].ff.ff,hcn[j].ss.ff,hcn[j].ff.ss,hcn[j].ss.ss,j);
// cerr<<j<<" !!"<<endl;
for (int u:tmp)
{
// cerr<<u<<endl;
res[u] = j;
xoa(1,1,m,hcn[u].ff.ff,{hcn[u].ff.ss,u});
xoa(1,1,m,hcn[u].ff.ff,{hcn[u].ss.ss,u});
xoa(1,1,m,hcn[u].ss.ff,{hcn[u].ff.ss,u});
xoa(1,1,m,hcn[u].ss.ff,{hcn[u].ss.ss,u});
}
}
for (int i=1; i<=n; i++) cout<<res[i]<<' '; cout<<'\n';
}
/**
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 'int main()':
circle_selection.cpp:120:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
120 | for (int i=1; i<=n; i++) cout<<res[i]<<' '; cout<<'\n';
| ^~~
circle_selection.cpp:120:49: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
120 | for (int i=1; i<=n; i++) cout<<res[i]<<' '; cout<<'\n';
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
112924 KB |
Output is correct |
| 2 |
Correct |
60 ms |
113052 KB |
Output is correct |
| 3 |
Incorrect |
54 ms |
112956 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3083 ms |
382836 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
113072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3094 ms |
507276 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
112924 KB |
Output is correct |
| 2 |
Correct |
60 ms |
113052 KB |
Output is correct |
| 3 |
Incorrect |
54 ms |
112956 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
112924 KB |
Output is correct |
| 2 |
Correct |
60 ms |
113052 KB |
Output is correct |
| 3 |
Incorrect |
54 ms |
112956 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
