This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
class Circle {
public:
ll x,y;
ll r;
int ind;
Circle(ll xx, ll yy, ll rr, int i){
x=xx;
y=yy;
r=rr;
ind=i;
}
bool operator<(const Circle& other) const{
if(r==other.r)return ind>other.ind;
return r<other.r;
}
};
ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=3e5+7;
ll n,m,k;
vector<Circle>d;
bool jnj[N];
bool isHatel(const Circle& a, const Circle& b){
ll xt=a.x-b.x;
ll yt=a.y-b.y;
ll rt=a.r+b.r;
return xt*xt+yt*yt<=rt*rt;
}
bool comp(const Circle& a, const Circle& b){
return a.x<b.x;
}
int main() {
cin>>n;
for(int i=0;i<n;i++){
int x,y,r;
cin>>x>>y>>r;
d.push_back(Circle(x,y,r,i));
}
vector<int>ans(n);
if(n<=5000){
sort(d.begin(),d.end());
reverse(d.begin(),d.end());
for(int i=0;i<n;i++){
// cout<<d[i].ind<<" ";
if(!jnj[d[i].ind]){
ans[d[i].ind]=d[i].ind;
jnj[d[i].ind]=true;
for(int j=0;j<n;j++){
if(!jnj[d[j].ind]&&isHatel(d[i],d[j])){
ans[d[j].ind]=d[i].ind;
jnj[d[j].ind]=true;
}
}
}
}
for(int x:ans)cout<<1+x<<" ";
cout<<endl;
return 0;
}
sort(d.begin(),d.end(),comp);
vector<int>p;
vector<int>rp(n);
for(int i=0;i<n;i++){
p.push_back(d[i].ind);
rp[d[i].ind]=i;
}
sort(d.begin(),d.end());
reverse(d.begin(),d.end());
for(int i=0;i<n;i++){
if(!jnj[d[i].ind]){
ans[d[i].ind]=d[i].ind;
jnj[d[i].ind]=true;
int ind=rp[d[i].ind];
int l=ind-1;
while(l>=0&&isHatel(d[p[l]],d[i])){
ans[d[p[l]].ind]=d[i].ind;
jnj[d[p[l]].ind]=true;
l--;
}
int r=ind+1;
while(r<n&&isHatel(d[p[r]],d[i])){
ans[d[p[r]].ind]=d[i].ind;
jnj[d[p[r]].ind]=true;
r++;
}
}
}
for(int x:ans)cout<<1+x<<" ";
cout<<endl;
}
# | 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... |