Submission #982272

#	Time	Username	Problem	Language	Result	Execution time	Memory
982272		Jawad_Akbar_JJ	Circle selection (APIO18_circle_selection)	C++17	7 / 100	2407 ms	101016 KiB

circle_selection

#include <iostream>
#include <set>

using namespace std;
#define int long long

const int N = 3e5 + 10;

int x[N];
int y[N];
int r[N];

int erased[N];

int dist(int i,int j){
	int xd = x[i] - x[j];
	int yd = y[i] - y[j];
	return xd * xd + yd * yd;
}

void sub1(int n){
	set<pair<int,int>> s;

	for (int i=1;i<=n;i++)
		s.insert({-r[i],i});

	while (s.size() > 0){
		int i = (*begin(s)).second;
		for (int j=1;j<=n;j++)
			if (!erased[j] and dist(i,j) <= (r[i] + r[j]) * (r[i] + r[j])){
				s.erase({-r[j],j});
				erased[j] = i;
			}
	}
	for (int i=1;i<=n;i++)
		cout<<erased[i]<<' ';
	cout<<'\n';
	exit(0);
}

void sub2(int n){
	set<pair<int,int>> s,X;

	for (int i=1;i<=n;i++){
		s.insert({-r[i],i});
		X.insert({x[i] - r[i],i});
		X.insert({x[i] + r[i],i});
		X.insert({x[i],i});
	}

	set<int> ind;

	while (s.size() > 0){
		int i = (*begin(s)).second;
		cout<<x[i]<<" "<<y[i]<<" "<<r[i]<<" "<<i<<endl;
		auto u = X.upper_bound({x[i] - r[i],0});
		while (u != X.end() and (*u).first <= x[i] + r[i]){
			ind.insert((*u).second);
			u = next(u);
		}

		for (int j : ind){
			if (erased[j])
				continue;
			erased[j] = i;
			s.erase({-r[j],j});
			X.erase({x[j] - r[j],j});
			X.erase({x[j] + r[j],j});
			X.erase({x[j],j});
		}
	}

	for (int i=1;i<=n;i++)
		cout<<erased[i]<<' ';
	cout<<'\n';
	exit(0);
}

signed main(){

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin>>n;

	for (int i=1;i<=n;i++){
		cin>>x[i]>>y[i]>>r[i];
		y[0] += y[i];
	}
	

	if (y[0] == 0)
		sub2(n);

	if (n <= 5000)
		sub1(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


// 10
// 1 0 1
// 3 0 1
// 5 0 2
// 7 0 1
// 9 0 3
// 11 0 1
// 13 0 2
// 15 0 1
// 16 0 1
// 17 0 1

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