Submission #1356867

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

circle_selection

#pragma GCC optimize("O3,Ofast,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 303030;

struct Circle {
    int x, y, r, id;
    bool doesIntersect(const Circle& rhs) const {
        ll dx = x - rhs.x;
        ll dy = y - rhs.y;
        ll pr = r + rhs.r;
        return dx * dx + dy * dy <= pr * pr;
    }
};

int div_floor(int a, int b) {
    int q = a / b;
    int r = a % b;

    if (r != 0 && ((r > 0) != (b > 0))) q--;
    return q;
}

int n, a[MAXN];
Circle cx[MAXN];

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

    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> cx[i].x >> cx[i].y >> cx[i].r; cx[i].id = i;
    }

    auto rescale = [&](int R) -> map<pair<int, int>, vector<Circle>> {
        map<pair<int, int>, vector<Circle>> res;
        for(int i = 1; i <= n; i++) {
            if(a[i]) continue;
            int r = cx[i].x / R;
            int c = cx[i].y / R;
            res[{r, c}].push_back(cx[i]);
        }
        return res;
    };

    int R = 1e9;

    vector<int> v(n);
    iota(v.begin(), v.end(), 1);
    sort(v.begin(), v.end(), [](int i, int j) { return tuple(-cx[i].r, i) < tuple(-cx[j].r, j); });

    auto table = rescale(R);

    for(auto i : v) {
        if(a[i]) continue;
        a[i] = i;

        int oldR = R;
        while(R/2 >= cx[i].r) R /= 2;
        if(oldR != R) table = rescale(R);

        int r = div_floor(cx[i].x, R);
        int c = div_floor(cx[i].y, R);
        for(int dr = -2; dr <= 2; dr++) {
            for(int dc = -2; dc <= 2; dc++) {
                for(auto c : table[{r+dr, c+dc}]) {
                    if(!a[c.id] && cx[i].doesIntersect(c)) a[c.id] = i;
                }
            }
        }
    }

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

Compilation message (stderr)

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from circle_selection.cpp:4:
/usr/include/c++/13/bits/allocator.h: In destructor 'constexpr std::_Rb_tree<std::pair<int, int>, std::pair<const std::pair<int, int>, std::vector<Circle> >, std::_Select1st<std::pair<const std::pair<int, int>, std::vector<Circle> > >, std::less<std::pair<int, int> >, std::allocator<std::pair<const std::pair<int, int>, std::vector<Circle> > > >::_Rb_tree_impl<std::less<std::pair<int, int> >, true>::~_Rb_tree_impl()':
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to 'always_inline' 'constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = std::_Rb_tree_node<std::pair<const std::pair<int, int>, std::vector<Circle> > >]': target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/map:62,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:152:
/usr/include/c++/13/bits/stl_tree.h:662:16: note: called from here
  662 |         struct _Rb_tree_impl
      |                ^~~~~~~~~~~~~