Submission #405640

#	Time	Username	Problem	Language	Result	Execution time	Memory
405640		rqi	Circle selection (APIO18_circle_selection)	C++14	7 / 100	3066 ms	25160 KiB

circle_selection

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pl> vpl;

#define f first
#define s second
#define pb push_back
#define mp make_pair

#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

struct hashFunc{
	size_t operator()(const pl& a) const {
		return a.f^(a.s+1);
	}
};

const int mx = 300005;
int n;
ll x[mx];
ll y[mx];
ll r[mx];

bool circIntersect(int a, int b){
	ll dist_sq = (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]);
	if(dist_sq <= (r[a]+r[b])*(r[a]+r[b])){
		return true;
	}
	return false;
}

vector<pair<ll, int>> buckets[35];
int ans[mx];
gp_hash_table<pl, vi, hashFunc> g;
ll GRID;

ll fdiv(ll a, ll b){
	assert(b >= 1);
	if(a >= 0) return a/b;
	return (a+1)/b-1;
}

pl gridReduce(pl a){
	return mp(fdiv(a.f, GRID), fdiv(a.s, GRID));
}

void remDup(vpl& a){
	sort(all(a));
	a.erase(unique(all(a)), a.end());
}

vpl getCorners(int circ){
	vpl corners = vpl{mp(x[circ]+r[circ], y[circ]+r[circ]), mp(x[circ]-r[circ], y[circ]+r[circ]), mp(x[circ]-r[circ], y[circ]-r[circ]), mp(x[circ]+r[circ], y[circ]-r[circ])};
	vector<pl> res;
	for(auto u: corners){
		res.pb(gridReduce(u));
	}
	remDup(res);
	return res;
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> x[i] >> y[i] >> r[i];
	}
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < 35; j++){
			if(r[i] < (1LL<<j)){
				buckets[j-1].pb(mp(-r[i], i));
				break;
			}
		}
	}
	assert(sz(buckets[30]) == 0);
	for(int k = 29; k >= 0; k--){
		sort(all(buckets[k]));
		g.clear();
		GRID = (1LL<<(k+2));
		for(int i = 1; i <= n; i++){
			if(ans[i] == 0){
				for(auto u: getCorners(i)){
					g[u].pb(i);
				}
			}
		}

		for(auto circ: buckets[k]){
			int ind = circ.s;
			if(ans[ind] == 0){
				for(auto u: getCorners(ind)){
					vi new_cands;
					for(auto cand: g[u]){
						if(ans[cand] != 0) continue;
						if(circIntersect(ind, cand)){
							ans[cand] = ind;
						}
						else{
							new_cands.pb(cand);
						}
					}
					g[u] = new_cands;
				}
				assert(ans[ind] == ind);
			}
		}
	}

	for(int i = 1; i <= n; i++){
		cout << ans[i] << " ";
	}
	cout << "\n";
}

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