Submission #705248

#	Time	Username	Problem	Language	Result	Execution time	Memory
705248		jeroenodb	Circle selection (APIO18_circle_selection)	C++17	100 / 100	2872 ms	23460 KiB

circle_selection

#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
typedef complex<int> pt;
#define X real()
#define Y imag()
auto cross(pt u, pt v) {return (ll)u.X*v.Y-(ll)u.Y*v.X;}
auto sgn(ll a) {return a==0?0:(a>0?1:-1);}
auto ccw(pt p1, pt p2, pt p3) {auto u = p2-p1, v = p3-p2;return cross(u,v);}
auto in(pt p1, pt p2) {return (ll)p1.X*p2.X+(ll)p1.Y*p2.Y;}
auto norm(pt p) {return (ll)p.X*p.X+(ll)p.Y*p.Y;}
bool comp(const pt& a, const pt& b) { return a.X<b.X or (a.X==b.X and a.Y < b.Y);}
void read(pt& p) {
    int a,b; cin >> a >> b;
    p = {a,b};
}

vi ans;
vector<pt> pts;
vi r;
struct cmp {
    bool operator()(int i, int j) const {
        return make_pair(pts[i].Y,i)<make_pair(pts[j].Y,j);
    }
};
bool xcomp(int i, int j) {
    return pts[i].X<pts[j].X;
}
bool rcomp(int i, int j) {
    return make_pair(-r[i],i)<make_pair(-r[j],j);
}
bool intersect(int i, int j) {
    return norm(pts[i]-pts[j])<=ll(r[i]+r[j])*(r[i]+r[j]);
}
vi rec(vi ord) {
    int n = ord.size();
    if(n<=1) {
        return ord;
    }
    int mid = n/2;
    auto kill = rec({ord.begin(),ord.begin()+mid});
    int rmid = r[ord[mid]];
    vi oord = ord;
    oord.erase(oord.begin(),oord.begin()+mid);
    
    for(int rep=0;rep<2;++rep) {
        sort(all(oord),xcomp);
        sort(all(kill),xcomp);
        multiset<int,cmp> s;
        int j=0;
        for(int i : oord) {
            while(j<(int)kill.size() and !xcomp(i,kill[j])) {
                s.insert(kill[j++]);
            }
            auto it = s.lower_bound(i);
            pt q = pts[i];
            while(it!=s.end()) {
                // consider this
                pt p = pts[*it];
                if(intersect(*it,i)) {
                    ans[i]=min(ans[i],*it,rcomp);
                }
                if(q.X-p.X>rmid+r[*it]) {
                    it = s.erase(it);
                } else if(q.X-p.X<abs(p.Y-q.Y)) {
                    break;
                } else ++it;
            }
            it = s.lower_bound(i);
            while(it!=s.begin()) {
                --it;
                pt p = pts[*it];
                if(intersect(*it,i)) {
                    ans[i]=min(ans[i],*it,rcomp);
                }
                if(q.X-p.X>rmid+r[*it]) {
                    it = s.erase(it);
                } else if(q.X-p.X<abs(p.Y-q.Y)) {
                    break;
                }
            }

        }
        for(auto& i : ord) pts[i] = {-pts[i].X,pts[i].Y};
    }
    oord.erase(partition(all(oord),[&](int i) {return ans[i]==i;}),oord.end());
    sort(all(oord),rcomp);
    auto kill2 = rec(oord);
    kill.insert(kill.begin(),all(kill2));
    return kill;

}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n; cin >> n;

    ans.resize(n),r.resize(n),pts.resize(n);
    iota(all(ans),0);
    for(int i=0;i<n;++i) read(pts[i]),cin >> r[i];
    vi ord = ans;
    sort(all(ord),rcomp);
    rec(ord);
    for(auto& i : ans) ++i;
    cout << ans << '\n';
    
    
}

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