Submission #771729

#	Time	Username	Problem	Language	Result	Execution time	Memory
771729		gagik_2007	Circle selection (APIO18_circle_selection)	C++17	7 / 100	352 ms	20336 KiB

circle_selection

#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 compRight(const Circle& a, const Circle& b){
    return a.x+a.r<b.x+b.r;
}

bool compLeft(const Circle& a, const Circle& b){
    return a.x-a.r<b.x-b.r;
}

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(),compLeft);
    vector<int>pl;
    vector<int>rpl(n);
    for(int i=0;i<n;i++){
        pl.push_back(d[i].ind);
        rpl[d[i].ind]=i;
    }
    sort(d.begin(),d.end(),compRight);
    vector<int>pr;
    vector<int>rpr(n);
    for(int i=0;i<n;i++){
        pr.push_back(d[i].ind);
        rpr[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=rpl[d[i].ind];
            int l=ind-1;
            while(l>=0&&isHatel(d[pl[l]],d[i])){
                ans[d[pl[l]].ind]=d[i].ind;
                jnj[d[pl[l]].ind]=true;
                l--;
            }
            int r=ind+1;
            while(r<n&&isHatel(d[pl[r]],d[i])){
                ans[d[pl[r]].ind]=d[i].ind;
                jnj[d[pl[r]].ind]=true;
                r++;
            }
            ind=rpr[d[i].ind];
            l=ind-1;
            while(l>=0&&isHatel(d[pr[l]],d[i])){
                ans[d[pr[l]].ind]=d[i].ind;
                jnj[d[pr[l]].ind]=true;
                l--;
            }
            r=ind+1;
            while(r<n&&isHatel(d[pr[r]],d[i])){
                ans[d[pr[r]].ind]=d[i].ind;
                jnj[d[pr[r]].ind]=true;
                r++;
            }
        }
    }
    for(int x:ans)cout<<1+x<<" ";
    cout<<endl;
}

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