| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 123933 | amiratou | 원 고르기 (APIO18_circle_selection) | C++14 | 0 ms | 0 KiB |
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;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define fi first
#define se second
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl;
#define sep() cerr << "--------------------" << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define int ll
#define ii pair<int,int>
#define v vector<int>
#define vii vector<ii>
#define vv vector<vector<ii> >
#define mp make_pair
#define INF 1000000000
#define pb push_back
#define EPS 1e-9
const int MOD = 1000000007; // 998244353
ii point[300005];
int r[300005];
struct node
{
int idx,prior,nb;
node *l,*r;
};
typedef node* pnode;
pnode root = NULL;
bool inter(int i,int j){
return ((point[i].fi-point[j].fi)*(point[i].fi-point[j].fi)+(point[i].se-point[j].se)*(point[i].se-point[j].se))<=((r[i]+r[j])*(r[i]+r[j]));
}
void update_sz(pnode &t){
if(t) t->nb=size(t->l)+size(t->r)+1;
}
void split(pnode t,pnode &l,pnode &r,int value){
if(!t)
l=r=NULL;
else if(t->key<value)
split(t->r,t->r,r,value),l=t;
else
split(t->l,l,t->l,value),r=t;
update_sz(t);
}
void insert(pnode &t, pnode it){
if(!t)
t=it;
else if(it->prior>t->prior)
split(t,it->l,it->r,it->key),t=it;
else
insert(inter(t->idx,it->idx)?t->r:t->l,it);
update_sz(t);
}
void merge(pnode &t,pnode l,pnode r){
if(!l || !r) t=l?l:r;
else if(l->prior>=r->prior)
merge(l->r,l->r,r),t=l;
else
merge(r->l,l,r->l),t=r;
update_sz(t);
}
vii vec;
bool mycomparer(std::pair<int, int> lhs, std::pair<int, int> rhs) {
if (lhs.first > rhs.first) {
return true;
}
else if (lhs.first == rhs.first && lhs.second < rhs.second) {
return true;
}
return false;
}
int ans[300005];
vv ad;
void righty(pnode t,vii &VV){
if(!t)
return ;
VV.pb({r[t->idx],t->idx});
righty(t->r,VV);
righty(t->l,VV);
}
void solve(pnode t){
if(!t)
return ;
vii VV;
VV.pb({r[t->idx],t->idx});
//ans[t->idx]=t->idx;
righty(t->r,VV);
ad.pb(VV);
solve(t->l);
}
main(){
//boost;
int n;
cin>>n;
for (int i = 0; i < n; ++i){
cin>>point[i].fi>>point[i].se>>r[i];
vec.pb({r[i],i});
}
sort(all(vec),mycomparer);
for (int i = 0; i < n; ++i){
pnode curr = new node;
curr->idx=vec[i].se;
curr->prior=rand();
curr->l=curr->r=NULL;
insert(root,curr);
}
solve(root);
for (int i = 0; i < sz(ad); ++i)
{
sort(all(ad[i]),mycomparer);
ans[ad[i][0].se]=ad[i][0].se;
for (int j = 1; j < sz(ad[i]); ++j)
ans[ad[i][j].se]=ad[i][0].se;
}
for (int i = 0; i < n; ++i)
cout<<ans[i]+1<<" ";
return 0;
}
//long long
//array bounds
//special cases
//binary search