Submission #1071015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071015		pawned	Circle selection (APIO18_circle_selection)	C++17	49 / 100	3083 ms	82268 KiB

circle_selection

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;

const char nl = '\n';

void fastIO() {
	ios::sync_with_stdio(false);
	cin.tie(0);
}

bool intersect(ll x1, ll y1, ll x2, ll y2, ll r1, ll r2) {
	ll dx = abs(x1 - x2);
	ll dy = abs(y1 - y2);
	ll dt = r1 + r2;
	if (dt * dt >= dx * dx + dy * dy)
		return true;
	return false;
}

int main() {
	fastIO();
	int N;
	cin>>N;
	vector<pair<ii, ll>> cr(N);
	// {{x, y}, r}
	multiset<pair<ii, ii>> all;
	// {{r, -id}, {x, y}}
	map<ll, set<pair<ll, ii>>> allx;	// maps x coord to all {y, {r, id}}
	for (int i = 0; i < N; i++) {
		ll x, y, r;
		cin>>x>>y>>r;
		all.insert({{r, -i}, {x, y}});
		allx[x].insert({y, {r, i}});
	}
	vi par(N, -1);
	int rem = N;
	while (rem > 0) {
		auto it = --all.end();
		ll r = (*it).fi.fi;
		int id = -(*it).fi.se;
		ll x = (*it).se.fi;
		ll y = (*it).se.se;
//		cout<<"at "<<id<<endl;
		// consider all from x in x-2r to x+2r, y in y-2r to r+2r
		auto it2 = allx.lower_bound(x - 2 * r);
		while (it2 != allx.end() && (*it2).fi <= x + 2 * r) {
			// do another search inside
			ll cx = (*it2).fi;
			vector<pair<ll, ii>> toremove;
			auto it3 = allx[cx].lower_bound({y - 2 * r, {-1, -1}});
			while (it3 != allx[cx].end() && (*it3).fi <= y + 2 * r) {
				ll cy = (*it3).fi;
				ll cr = (*it3).se.fi;
				int cid = (*it3).se.se;
				if (intersect(x, y, cx, cy, r, cr)) {
					toremove.pb(*it3);
				}
				it3++;
			}
			for (pair<ll, ii> p : toremove) {
				par[p.se.se] = id;
//				cout<<"erased "<<p.se.se<<endl;
				allx[cx].erase(p);
				all.erase({{p.se.fi, -p.se.se}, {cx, p.fi}});
				rem--;
			}
			it2++;
		}
	}
//	cout<<"ANSWER: ";
	for (int x : par)
		cout<<(x + 1)<<" ";
	cout<<endl;
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:63:9: warning: unused variable 'cid' [-Wunused-variable]
   63 |     int cid = (*it3).se.se;
      |         ^~~

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