Submission #57812

#	Time	Username	Problem	Language	Result	Execution time	Memory
57812		robert	Circle selection (APIO18_circle_selection)	C++14	7 / 100	3050 ms	30856 KiB

circle_selection

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> ii;

int ans[100100];
pair<ii, int> c[100100];
ii cs[100100];
int act[100100];
int N;

long long pow(long long g, long long e){
	if(e==0){
		return 1;
	} else {
		long long tmp = pow(g, e>>1);
		tmp*=tmp;
		if(e&1)
			tmp *= g;
		return tmp;
	}
}

long long d(int a, int b){
	return pow(c[a].first.second-c[b].first.second, 2)+pow(c[b].first.first-c[a].first.first, 2);
}

void eliminate(int i){
	for(int n=0; n<N; n++){
		if(d(n, i)<=pow(c[n].second+c[i].second, 2)){
		//	cout << i << " " << n << " " << d(n, i) << endl;
			if(act[n]){
				act[n] = 0;
				ans[n] = i;
			}
		}
	}
}

int main(){
	cin>>N;
	for(int n=0; n<N; n++){
		cin>>c[n].first.first>>c[n].first.second>>c[n].second;
		cs[n].first = c[n].second;
		cs[n].second = -n;
		act[n] = 1;
	}
	sort(cs, cs+N);
	reverse(cs, cs+N);
	for(int n=0; n<N; n++){
		//cout << -cs[n].second << endl;
		if(act[-cs[n].second]){
			eliminate(-cs[n].second);
		}
	}
	for(int n=0; n<N; n++){
		if(n)
			cout << " ";
		cout << (ans[n]+1);
	}
	cout << endl;

	return 0;
}

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