제출 #387878

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
387878		talant117408	원 고르기 (APIO18_circle_selection)	C++17	12 / 100	976 ms	40072 KiB

circle_selection

/*
    Code written by Talant I.D.
*/
#include <bits/stdc++.h>
 
using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;
 
int mod;
 
ll mode(ll a) {
    a %= mod;
    if (a < 0) a += mod;
    return a;
}
 
ll subt(ll a, ll b) {
    return mode(mode(a)-mode(b));
}
 
ll add(ll a, ll b) {
    return mode(mode(a)+mode(b));
}
 
ll mult(ll a, ll b) {
    return mode(mode(a)*mode(b));
}
 
ll binpow(ll a, ll b, ll m) {
    ll res = 1;
    while (b) {
        if (b&1) res = ((res*a)%m+m)%m;
        a = ((a*a)%m+m)%m;
        b >>= 1;
    }
    return res;
}

const int N = 3e5+7;
int removedBy[N], adjacentTo[N], adjacentTimes[N];
int x[N], y[N], R[N];

bool intersect(int i1, int i2) {
	return ll(ll(x[i1]-x[i2])*ll(x[i1]-x[i2])+ll(y[i1]-y[i2])*ll(y[i1]-y[i2])) <= ll(ll(R[i1]+R[i2])*ll(R[i1]+R[i2]));
}

int main() {
	do_not_disturb
    //~ usaco("marathon");
	
	int n;
	cin >> n;
	bool allZeroes = 1;
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> y[i] >> R[i];
		if (y[i]) allZeroes = 0;
	}
	
	vector <pair <pii, pii>> points;
	auto cmp = [&](pair <pii, pii> a, pair <pii, pii> b) {
		if (a.first.first == b.first.first) return a.first.second < b.first.second;
		return a.first.first > b.first.first;
	};
	
	if (allZeroes) {
		for (int i = 0; i < n; i++) {
			points.pb(mp(mp(R[i], i+1), mp(x[i]-R[i], x[i]+R[i])));
		}
		sort(all(points), cmp);
		set <pii> byL, byR;
		for (auto to : points) byL.insert(mp(to.second.first, to.first.second));
		for (auto to : points) byR.insert(mp(to.second.second, to.first.second));
		
		for (auto to : points) {
			auto l = to.second.first, r = to.second.second;
			auto ind = to.first.second;
			if (removedBy[ind]) {
				continue;
			}
			auto it = byL.lb(mp(l, 0));
			while (it != byL.end() && (*it).first <= r) {
				removedBy[(*it).second] = ind;
				byR.erase(mp(x[(*it).second-1]+R[(*it).second-1], (*it).second));
				byL.erase(it);
				it = byL.lb(mp(l, 0));
			}
			auto it2 = byR.ub(mp(r, 2e9));
			while (it2 != byR.begin() && (*--it2).first >= l) {
				removedBy[(*it2).second] = ind;
				byL.erase(mp(x[(*it2).second-1]-R[(*it2).second-1], (*it2).second));
				byR.erase(it2);
				it2 = byR.ub(mp(r, 2e9));
			}
		}
	}
	else {
		for (int i = 0; i < n; i++) {
			points.pb(mp(mp(R[i], i+1), mp(x[i]-R[i], x[i]+R[i])));
		}
		sort(all(points), cmp);
		set <pii> markers;
		vector <pair <int, pii>> Ys;
		for (int i = 0; i < n; i++) {
			Ys.pb(mp(y[i]-R[i], mp(0, i)));
			Ys.pb(mp(y[i]+R[i], mp(1, i)));
		}
		sort(all(Ys));
		for (int i = 0; i < n*2; i++) {
			auto type = Ys[i].second.first, ind = Ys[i].second.second;
			if (!type) {
				markers.insert(mp(x[ind], ind));
				auto it = markers.lb(mp(x[ind], ind));
				if (it != markers.begin()) {
					auto pr = next(it, -1);
					if (intersect((*it).second, (*pr).second)) {
						adjacentTo[(*it).second] = (*pr).second+1;
						adjacentTo[(*pr).second] = (*it).second+1;
						adjacentTimes[(*it).second]++;
						adjacentTimes[(*pr).second]++;
					}
				}
				if (next(it, 1) != markers.end()) {
					auto nx = next(it, 1);
					if (intersect((*it).second, (*nx).second)) {
						adjacentTo[(*it).second] = (*nx).second+1;
						adjacentTo[(*nx).second] = (*it).second+1;
						adjacentTimes[(*it).second]++;
						adjacentTimes[(*nx).second]++;
					}
				}
			}
			else {
				auto it = markers.lb(mp(x[ind], ind));
				if (it != markers.begin() && next(it, 1) != markers.end()) {
					auto nx = next(it, 1);
					auto pr = next(it, -1);
					if (intersect((*nx).second, (*pr).second)) {
						adjacentTo[(*nx).second] = (*pr).second+1;
						adjacentTo[(*pr).second] = (*nx).second+1;
						adjacentTimes[(*nx).second]++;
						adjacentTimes[(*pr).second]++;
					}
				}
				markers.erase(it);
			}
		}
		
		bool onlyOne = 1;
		for (int i = 0; i < n; i++) {
			if (adjacentTimes[i] > 1) onlyOne = 0;
		}
		if (!onlyOne) return 0;
		for (int i = 0; i < n; i++) {
			auto ind = points[i].first.second;
			if (removedBy[ind]) continue;
			removedBy[ind] = ind;
			removedBy[adjacentTo[ind-1]] = ind;
		}
	}
	
	for (int i = 1; i <= n; i++) {
		cout << removedBy[i] << ' ';
	}
		
    return 0;
}
/*
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: 12 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13