Submission #544147

#	Time	Username	Problem	Language	Result	Execution time	Memory
544147		amunduzbaev	Circle selection (APIO18_circle_selection)	C++17	0 / 100	445 ms	26864 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);
	vector<int> tot;
	for(int i=0;i<n;i++){
		cin>>a[i].x>>a[i].y>>a[i].r;
	}
	int R = a[0].r;
	for(int i=0;i<n;i++) tot.push_back(a[i].x / R);
	sort(tot.begin(), tot.end());
	tot.erase(unique(tot.begin(), tot.end()), tot.end());
	vector<set<ar<int, 2>>> pp(tot.size());
	
	for(int i=0;i<n;i++){
		auto j = lower_bound(tot.begin(), tot.end(), a[i].x / R) - tot.begin();
		assert(j < (int)tot.size());
		pp[j].insert({a[i].y, i});
	}
	
	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 (R + R - dis(i, j) > eps);
	};
	
	vector<int> used(n);
	for(int i=0;i<n;i++){
		if(used[i]) continue;
		int l = lower_bound(tot.begin(), tot.end(), a[i].x / R - 2) - tot.begin();
		int r = upper_bound(tot.begin(), tot.end(), a[i].x / R + 2) - tot.begin();
		for(int j=l;j<r;j++){
			int lx = (a[i].y / R - 2) * R;
			int rx = (a[i].y / R + 3) * R;
			auto it = pp[j].lower_bound({lx, -1});
			vector<ar<int, 2>> er;
			while(it != pp[j].end() && (*it)[0] < rx){
				if(check((*it)[1], i)){
					er.push_back(*it);
				} it++;
			}
			
			for(auto x : er) pp[j].erase(x), used[x[1]] = i + 1;
		}
		assert(used[i] == i + 1);
	}
	
	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: 0 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13