제출 #1201675

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1201675		crispxx	원 고르기 (APIO18_circle_selection)	C++20	19 / 100	1000 ms	70376 KiB

circle_selection

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

#define int long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'

template <typename A, typename B>
bool chmin(A &a, const B &b) {
	if(a > b) {
		return a = b, true;
	}
	return false;
}

template <typename A, typename B>
bool chmax(A &a, const B &b) {
	if(a < b) {
		return a = b, true;
	}
	return false;
}

void solve() {
	int n; cin >> n;
	
	vector<int> x(n), y(n), r(n);
	
	for(int i = 0; i < n; i++) {
		cin >> x[i] >> y[i] >> r[i];
	}
	
	if(n <= 5000) {
		set<pair<int, int>, greater<>> st;
		
		for(int i = 0; i < n; i++) {
			st.emplace(r[i], -i);
		}
		
		vector<int> deled(n);
		
		while(!st.empty()) {
			auto [rad, i] = *st.begin();
			i = -i;
			vector<int> del;
			for(auto [rad2, j] : st) {
				j = -j;
				int a = x[i] - x[j], b = y[i] - y[j], c = r[i] + r[j];
				if(a * a + b * b <= c * c) {
					del.pb(j);
				}
			}
			for(auto j : del) {
				st.erase({r[j], -j});
				deled[j] = i;
			}
		}
		
		for(auto i : deled) cout << i + 1 << ' ';
		cout << nl;
		return;
	}
	
	set<pair<int, int>> rng;
	set<pair<int, int>, greater<>> st;
	
	for(int i = 0; i < n; i++) {
		rng.emplace(x[i] - r[i], i);
		rng.emplace(x[i] + r[i], i);
		st.emplace(r[i], -i);
	}
	
	vector<int> deled(n);
	
	while(!st.empty()) {
		auto [rad, i] = *st.begin();
		i = -i;
		vector<int> del;
		for(auto it = rng.lower_bound({x[i] - r[i], 0}); it != rng.end(); it++) {
			if(it -> first > x[i] + r[i]) break;
			del.pb(it -> second);
		}
		for(auto j : del) {
			st.erase({r[j], -j});
			rng.erase({x[j] - r[j], j});
			rng.erase({x[j] + r[j], j});
			deled[j] = i;
		}
	}
	
	for(auto i : deled) cout << i + 1 << ' ';
	cout << nl;
}

/**

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


**/

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	solve();
}

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