Submission #544199

#	Time	Username	Problem	Language	Result	Execution time	Memory
544199		amunduzbaev	Circle selection (APIO18_circle_selection)	C++17	100 / 100	2646 ms	42324 KiB

circle_selection

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

#define ar array
#define int long long
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);
	vector<vector<ar<int, 2>>> pp;
	vector<int> used(n), tot, par(n);
	int R;
	auto get = [&](int x){ 
		if(x >= 0) return x / R;
		else {
			return (x + 1) / R - 1;
		}
	};
	
	auto rec = [&](){
		pp.clear(); tot.clear();
		for(int i=0;i<n;i++) {
			if(used[i]) continue;
			tot.push_back(get(a[i].x));
		}
		sort(tot.begin(), tot.end());
		tot.erase(unique(tot.begin(), tot.end()), tot.end());
		pp.resize(tot.size());
		for(int i=0;i<n;i++){
			if(used[i]) continue;
			auto j = lower_bound(tot.begin(), tot.end(), get(a[i].x)) - tot.begin();
			//~ assert(j < (int)tot.size());
			pp[j].push_back({a[i].y, i});
		}
		
		for(int i=0;i<(int)tot.size();i++){
			sort(pp[i].begin(), pp[i].end());
			for(int j=0;j<(int)pp[i].size();j++){
				par[pp[i][j][1]] = j + 1;
			}
		}
	};
	
	vector<int> p(n); 
	for(int i=0;i<n;i++){
		p[i] = i;
		cin>>a[i].x>>a[i].y>>a[i].r;
	}
	sort(p.begin(), p.end(), [&](int i, int j){
		if(a[i].r != a[j].r)
			return (a[i].r > a[j].r);
		else 
			return i < j;
	});
	
	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){
		return (a[i].r + a[j].r >= dis(i, j));
	};
	
	R = a[p[0]].r;
	rec();
	for(auto i : p){
		if(used[i]) continue;
		if(a[i].r * 2 <= R) R = a[i].r, rec();
		int l = lower_bound(tot.begin(), tot.end(), get(a[i].x) - 2) - tot.begin();
		int r = upper_bound(tot.begin(), tot.end(), get(a[i].x) + 2) - tot.begin();
		int lx = (get(a[i].y) - 2) * R;
		int rx = (get(a[i].y) + 3) * R;
		
		function<int(int, int)> f = [&](int j, int i){
			if(i >= (int)pp[j].size() || !used[pp[j][i][1]]) return i;
			par[pp[j][i][1]] = f(j, par[pp[j][i][1]]);
			return par[pp[j][i][1]];
		};
		
		for(int j=l;j<r;j++){
			int it = lower_bound(pp[j].begin(), pp[j].end(), (ar<int, 2>){lx, -1}) - pp[j].begin();
			it = f(j, it);
			while(it < (int)pp[j].size() && pp[j][it][0] < rx){
				if(check(pp[j][it][1], i)){
					used[pp[j][it][1]] = i + 1;
				}
				
				it = par[pp[j][it][1]];
				it = f(j, it);
			}
		}
	}
	
	for(int i=0;i<n;i++) cout<<used[i]<<" ";
	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: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 30 / 30
• Subtask 6: 13 / 13