Submission #1160137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160137		xnqs	Circle selection (APIO18_circle_selection)	C++20	Compilation error	0 ms	0 KiB

circle_selection

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <map>

struct Circle {
	int x, y, r, idx;
	Circle():
		x(0), y(0), r(0), idx(0) {}
	Circle(int x, int y, int r, int idx):
		x(x), y(y), r(r), idx(idx) {}

	bool operator == (const Circle& other) const {
		if (this->x!=other.x) return 0;
		if (this->y!=other.y) return 0;
		if (this->r!=other.r) return 0;
		if (this->idx!=other.idx) return 0;
		return 1;
	}
};

struct PairHasher {
	std::size_t operator() (const std::pair<int,int>& p) const {
		return p.first * 1000000006ULL + p.second;
	}
};

int n;
std::unordered_set<int> active;
std::vector<Circle> circles;
std::vector<int> eliminator;
int idx_r[500005];

int grid_size;
std::map<std::pair<int,int>, std::vector<int>, PairHasher> grid;

inline int64_t euclid_dist(const Circle& a, const Circle& b) {
	return 1LL*(a.x-b.x)*(a.x-b.x) + 1LL*(a.y-b.y)*(a.y-b.y);
}

/*
	d(a,b) - a.r <= b.r
	sqrt((a.x-b.x)^2 + (a.y-b.y)^2) - a.r <= b.r
	sqrt((a.x-b.x)^2 + (a.y-b.y)^2) <= b.r + a.r
	(a.x-b.x)^2 + (a.y-b.y)^2 <= (b.r + a.r)^2
*/
inline bool intersect(const Circle& a, const Circle& b) {
	return euclid_dist(a,b) <= 1LL*(a.r+b.r)*(a.r+b.r);
}

void init_grid(int size) {
	grid.clear();
	grid_size = size;
	for (auto i : active) {
		grid[std::pair<int,int>(circles[i].x/size,circles[i].y/size)].emplace_back(i);
	}
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> n;
	for (int i = 0, x, y, r; i < n; i++) {
		active.emplace(i);
		std::cin >> x >> y >> r;
		circles.emplace_back(x,y,r,i);
	}

	std::sort(circles.begin(),circles.end(),[](const Circle& a, const Circle& b) {
		if (a.r!=b.r) return a.r > b.r;
		return a.idx < b.idx;
	});

	for (int i = 0; i < n; i++) {
		idx_r[circles[i].idx] = i;
	}

	eliminator.assign(n, 0);
	init_grid(2*circles[0].r);
	for (const auto& c : circles) {
		const auto& [x, y, r, idx] = c;
		if (2*r < grid_size/2) {
			init_grid(2*r);
		}
		if (eliminator[idx]) {
			continue;
		}

		eliminator[idx] = idx+1;
		active.erase(idx_r[idx]);

		//std::cout << idx << " " << grid_size << "\n";

		int grid_x = x / grid_size;
		int grid_y = y / grid_size;

		for (int gx = grid_x-2; gx <= grid_x+2; gx++) {
			for (int gy = grid_y-2; gy <= grid_y+2; gy++) {
				auto& tmp = grid[std::pair<int,int>(gx,gy)];
				for (auto it = tmp.begin(); it != tmp.end();) {
					int i = *it;
					if (eliminator[circles[i].idx]) {
						++it;
						continue;
					}

					if (intersect(c, circles[i])) {
						eliminator[circles[i].idx] = idx+1;
						active.erase(idx_r[circles[i].idx]);
						//it = tmp.erase(it);
						++it;
					}
					else {
						++it;
					}
				}
			}
		}
	}

	for (int i = 0; i < n; i++) {
		std::cout << eliminator[i] << " ";
	}
	std::cout << "\n";
}

Compilation message (stderr)

In file included from /usr/include/c++/11/map:61,
                 from circle_selection.cpp:14:
/usr/include/c++/11/bits/stl_map.h: In instantiation of 'std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](std::map<_Key, _Tp, _Compare, _Alloc>::key_type&&) [with _Key = std::pair<int, int>; _Tp = std::vector<int>; _Compare = PairHasher; _Alloc = std::allocator<std::pair<const std::pair<int, int>, std::vector<int> > >; std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = std::vector<int>; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<int, int>]':
circle_selection.cpp:65:63:   required from here
/usr/include/c++/11/bits/stl_map.h:519:39: error: no match for call to '(std::map<std::pair<int, int>, std::vector<int>, PairHasher>::key_compare {aka PairHasher}) (std::map<std::pair<int, int>, std::vector<int>, PairHasher>::key_type&, const std::pair<int, int>&)'
  519 |         if (__i == end() || key_comp()(__k, (*__i).first))
      |                             ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
circle_selection.cpp:33:21: note: candidate: 'std::size_t PairHasher::operator()(const std::pair<int, int>&) const'
   33 |         std::size_t operator() (const std::pair<int,int>& p) const {
      |                     ^~~~~~~~
circle_selection.cpp:33:21: note:   candidate expects 1 argument, 2 provided
In file included from /usr/include/c++/11/set:60,
                 from circle_selection.cpp:13:
/usr/include/c++/11/bits/stl_tree.h: In instantiation of 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_lower_bound(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Link_type, std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Base_ptr, const _Key&) [with _Key = std::pair<int, int>; _Val = std::pair<const std::pair<int, int>, std::vector<int> >; _KeyOfValue = std::_Select1st<std::pair<const std::pair<int, int>, std::vector<int> > >; _Compare = PairHasher; _Alloc = std::allocator<std::pair<const std::pair<int, int>, std::vector<int> > >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<int, int>, std::pair<const std::pair<int, int>, std::vector<int> >, std::_Select1st<std::pair<const std::pair<int, int>, std::vector<int> > >, PairHasher, std::allocator<std::pair<const std::pair<int, int>, std::vector<int> > > >::iterator; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Link_type = std::_Rb_tree_node<std::pair<const std::pair<int, int>, std::vector<int> > >*; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Base_ptr = std::_Rb_tree_node_base*]':
/usr/include/c++/11/bits/stl_tree.h:1270:30:   required from 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::lower_bound(const key_type&) [with _Key = std::pair<int, int>; _Val = std::pair<const std::pair<int, int>, std::vector<int> >; _KeyOfValue = std::_Select1st<std::pair<const std::pair<int, int>, std::vector<int> > >; _Compare = PairHasher; _Alloc = std::allocator<std::pair<const std::pair<int, int>, std::vector<int> > >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<int, int>, std::pair<const std::pair<int, int>, std::vector<int> >, std::_Select1st<std::pair<const std::pair<int, int>, std::vector<int> > >, PairHasher, std::allocator<std::pair<const std::pair<int, int>, std::vector<int> > > >::iterator; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::key_type = std::pair<int, int>]'
/usr/include/c++/11/bits/stl_map.h:1259:32:   required from 'std::map<_Key, _Tp, _Compare, _Alloc>::iterator std::map<_Key, _Tp, _Compare, _Alloc>::lower_bound(const key_type&) [with _Key = std::pair<int, int>; _Tp = std::vector<int>; _Compare = PairHasher; _Alloc = std::allocator<std::pair<const std::pair<int, int>, std::vector<int> > >; std::map<_Key, _Tp, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<int, int>, std::pair<const std::pair<int, int>, std::vector<int> >, std::_Select1st<std::pair<const std::pair<int, int>, std::vector<int> > >, PairHasher, std::allocator<std::pair<const std::pair<int, int>, std::vector<int> > > >::iterator; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<int, int>]'
/usr/include/c++/11/bits/stl_map.h:517:28:   required from 'std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](std::map<_Key, _Tp, _Compare, _Alloc>::key_type&&) [with _Key = std::pair<int, int>; _Tp = std::vector<int>; _Compare = PairHasher; _Alloc = std::allocator<std::pair<const std::pair<int, int>, std::vector<int> > >; std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = std::vector<int>; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<int, int>]'
circle_selection.cpp:65:63:   required from here
/usr/include/c++/11/bits/stl_tree.h:1905:36: error: no match for call to '(PairHasher) (const std::pair<int, int>&, const std::pair<int, int>&)'
 1905 |         if (!_M_impl._M_key_compare(_S_key(__x), __k))
      |              ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
circle_selection.cpp:33:21: note: candidate: 'std::size_t PairHasher::operator()(const std::pair<int, int>&) const'
   33 |         std::size_t operator() (const std::pair<int,int>& p) const {
      |                     ^~~~~~~~
circle_selection.cpp:33:21: note:   candidate expects 1 argument, 2 provided
In file included from /usr/include/c++/11/set:60,
                 from circle_selection.cpp:13:
/usr/include/c++/11/bits/stl_tree.h: In instantiation of 'static const _Key& std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_S_key(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type) [with _Key = std::pair<int, int>; _Val = std::pair<const std::pair<int, int>, std::vector<int> >; _KeyOfValue = std::_Select1st<std::pair<const std::pair<int, int>, std::vector<int> > >; _Compare = PairHasher; _Alloc = std::allocator<std::pair<const std::pair<int, int>, std::vector<int> > >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type = const std::_Rb_tree_node<std::pair<const std::pair<int, int>, std::vector<int> > >*]':
/usr/include/c++/11/bits/stl_tree.h:1905:36:   required from 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_lower_bound(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Link_type, std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Base_ptr, const _Key&) [with _Key = std::pair<int, int>; _Val = std::pair<const std::pair<int, int>, std::vector<int> >; _KeyOfValue = std::_Select1st<std::pair<const std::pair<int, int>, std::vector<int> > >; _Compare = PairHasher; _Alloc = std::allocator<std::pair<const std::pair<int, int>, std::vector<int> > >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<int, int>, std::pair<const std::pair<int, int>, std::vector<int> >, std::_Select1st<std::pair<const std::pair<int, int>, std::vector<int> > >, PairHasher, std::allocator<std::pair<const std::pair<int, int>, std::vector<int> > > >::iterator; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Link_type = std::_Rb_tree_node<std::pair<const std::pair<int, int>, std::vector<int> > >*; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Base_ptr = std::_Rb_tree_node_base*]'
/usr/include/c++/11/bits/stl_tree.h:1270:30:   required from 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::lower_bound(const key_type&) [with _Key = std::pair<int, int>; _Val = std::pair<const std::pair<int, int>, std::vector<int> >; _KeyOfValue = std::_Select1st<std::pair<const std::pair<int, int>, std::vector<int> > >; _Compare = PairHasher; _Alloc = std::allocator<std::pair<const std::pair<int, int>, std::vector<int> > >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<int, int>, std::pair<const std::pair<int, int>, std::vector<int> >, std::_Select1st<std::pair<const std::pair<int, int>, std::vector<int> > >, PairHasher, std::allocator<std::pair<const std::pair<int, int>, std::vector<int> > > >::iterator; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::key_type = std::pair<int, int>]'
/usr/include/c++/11/bits/stl_map.h:1259:32:   required from 'std::map<_Key, _Tp, _Compare, _Alloc>::iterator std::map<_Key, _Tp, _Compare, _Alloc>::lower_bound(const key_type&) [with _Key = std::pair<int, int>; _Tp = std::vector<int>; _Compare = PairHasher; _Alloc = std::allocator<std::pair<const std::pair<int, int>, std::vector<int> > >; std::map<_Key, _Tp, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<int, int>, std::pair<const std::pair<int, int>, std::vector<int> >, std::_Select1st<std::pair<const std::pair<int, int>, std::vector<int> > >, PairHasher, std::allocator<std::pair<const std::pair<int, int>, std::vector<int> > > >::iterator; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<int, int>]'
/usr/include/c++/11/bits/stl_map.h:517:28:   required from 'std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](std::map<_Key, _Tp, _Compare, _Alloc>::key_type&&) [with _Key = std::pair<int, int>; _Tp = std::vector<int>; _Compare = PairHasher; _Alloc = std::allocator<std::pair<const std::pair<int, int>, std::vector<int> > >; std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = std::vector<int>; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<int, int>]'
circle_selection.cpp:65:63:   required from here
/usr/include/c++/11/bits/stl_tree.h:762:23: error: static assertion failed: comparison object must be invocable with two arguments of key type
  762 |         static_assert(__is_invocable<_Compare&, const _Key&, const _Key&>{},
      |                       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/11/bits/stl_tree.h:762:23: note: 'std::__is_invocable<PairHasher&, const std::pair<int, int>&, const std::pair<int, int>&>{}' evaluates to false