Submission #123924

#	Time	Username	Problem	Language	Result	Execution time	Memory
123924		amiratou	Circle selection (APIO18_circle_selection)	C++14	7 / 100	3055 ms	16188 KiB

circle_selection

#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<int> >
#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;
    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 insert(pnode &t, pnode it){
    if(!t)
        t=it;
    //debugs(t->idx,it->idx);
    //debug(inter(t->idx,it->idx));
    else if(inter(t->idx,it->idx))
        insert(t->r,it);
    else
        insert(t->l,it);
}
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];
void righty(pnode t,int id){
    if(!t)
        return ;
    ans[t->idx]=id;
    righty(t->r,id);
    righty(t->l,id);
}
void solve(pnode t){
    if(!t)
        return ;
    ans[t->idx]=t->idx;
    righty(t->r,t->idx);
    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->l=curr->r=NULL;
        insert(root,curr);
    }
    solve(root);
    for (int i = 0; i < n; ++i)
        cout<<ans[i]+1<<" ";
    return 0;
}
//long long
//array bounds
//special cases
//binary search

Compilation message (stderr)

circle_selection.cpp:70:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

• Subtask 1: 7 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13