Submission #544131

#	Time	Username	Problem	Language	Result	Execution time	Memory
544131		amunduzbaev	Circle selection (APIO18_circle_selection)	C++17	15 / 100	545 ms	19028 KiB

circle_selection

#include "bits/stdc++.h"
using namespace std;

#define ar array
const double eps = 1e-9;

struct poi{
	int x, y, r;
};

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	vector<poi> a(n);
	for(int i=0;i<n;i++){
		cin>>a[i].x>>a[i].y>>a[i].r;
	}
	
	vector<int> in(n); iota(in.begin(), in.end(), 0);
	vector<int> out(n); iota(out.begin(), out.end(), 0);
	sort(in.begin(), in.end(), [&](int i, int j){
		return (a[i].x - a[i].r < a[j].x - a[j].r);
	});
	
	sort(out.begin(), out.end(), [&](int i, int j){
		return (a[i].x + a[i].r < a[j].x + a[j].r);
	});
	
	set<ar<int, 2>> ss;
	vector<int> par(n, -1);
	
	auto sq = [&](int x) { return x * 1ll * x; };
	auto dis = [&](int i, int j) -> double{
		return sqrt(sq(a[i].x - a[j].x) + sq(a[i].y - a[j].y));
	};
	
	auto check = [&](int i, int j){
		if(a[i].r + a[j].r - dis(i, j) > eps){
			par[i] = j, par[j] = i;
		}
	};
	
	auto add = [&](int i){
		auto it = ss.lower_bound({a[i].y, i});
		if(it != ss.end()) check((*it)[1], i);
		if(it != ss.begin()) check((*--it)[1], i);
		ss.insert({a[i].y, i});
	};
	
	auto del = [&](int i){
		ss.erase({a[i].y, i});
		auto it = ss.lower_bound({a[i].y, i});
		if(it != ss.end() && it != ss.begin()){
			auto L = it; L--;
			check((*it)[1], (*L)[1]);
		}
	};
	
	int j=0;
	for(auto i : in){
		while(j < n && a[out[j]].x + a[out[j]].r < a[i].x - a[i].r){
			del(out[j++]);
		}
		
		add(i);
	}
	
	for(int i=0;i<n;i++){
		if(par[i] == -1) cout<<i + 1<<" ";
		else {
			if(a[par[i]].r > a[i].r || (a[par[i]].r == a[i].r && par[i] < i)) cout<<par[i] + 1<<" ";
			else cout<<i + 1<<" ";
		}
	}
	
	cout<<"\n";
}

/*

11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1

*/

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