Submission #1071011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071011		pawned	Circle selection (APIO18_circle_selection)	C++17	49 / 100	3083 ms	73000 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<int, int> ii;
typedef vector<int> vi;

const char nl = '\n';

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

bool intersect(int &x1, int &y1, int &x2, int &y2, int &r1, int &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, int>> cr(N);
	// {{x, y}, r}
	set<pair<ii, ii>> all;
	// {{r, -id}, {x, y}}
	map<int, set<pair<int, ii>>> allx;	// maps x coord to all {y, {r, id}}
	for (int i = 0; i < N; i++) {
		int 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();
		int r = (*it).fi.fi;
		int id = -(*it).fi.se;
		int x = (*it).se.fi;
		int 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
		int xl = max((ll)(x) - 2 * (ll)(r), (ll)(-2e9));
		int xh = min((ll)(x) + 2 * (ll)(r), (ll)(2e9));
		auto it2 = allx.lower_bound(xl);
		while (it2 != allx.end() && (*it2).fi <= xh) {
			// do another search inside
			int cx = (*it2).fi;
			vector<pair<ll, ii>> toremove;
			int dx = abs(x - cx);
			// can do up to sqrt for yh
			ll dy = (ll)(pow(4 * (double)(r) * (double)(r) - (double)(dx) * (double)(dx), 0.5) + 1);
			int yl = max((ll)(y) - dy, (ll)(-2e9));
			int yh = min((ll)(y) + dy, (ll)(2e9));
			auto it3 = allx[cx].lower_bound({yl, {-1, -1}});
			while (it3 != allx[cx].end() && (*it3).fi <= yh) {
				int cy = (*it3).fi;
				int cr = (*it3).se.fi;
				if (intersect(x, y, cx, cy, r, cr)) {
					toremove.pb(*it3);
				}
				it3++;
			}
			for (pair<int, 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;
}

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