Submission #261162

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
261162	2020-08-11T13:04:47 Z	SorahISA	Circle selection (APIO18_circle_selection)	C++17	Compilation error	0 ms	0 KB

circle_selection

#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/extc++.h>
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double
using pii = pair<int, int>;
template<typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using Prior = std::priority_queue<T>;

#define X first
#define Y second
#define ALL(x) (x).begin(), (x).end()
#define eb emplace_back
#define pb push_back
#define fastIO() ios_base::sync_with_stdio(false), cin.tie(0)


const int INF = 0x7f7f7f7f;
const int maxn = 3E5 + 5;
int R;

struct Circle {
    int x, y, r, id;
    bool operator < (const Circle &rhs) const {
        if (r == rhs.r) return id > rhs.id;
        return r < rhs.r;
    }
};

int32_t main() {
    fastIO();
    
    int n;
    cin >> n;
    
    Prior<Circle> pq;
    vector<Circle> cir(n);
    for (int i = 0; i < n; ++i) {
        cin >> cir[i].x >> cir[i].y >> cir[i].r;
        cir[i].id = i;
        pq.push(cir[i]);
    }
    
    R = cir[0].r;
    __gnu_pbds::gp_hash_table<pii, set<int>> cid;
    for (int i = 0; i < n; ++i) {
        cid[{cir[i].x / R, cir[i].y / R}].insert(cir[i].id);
    }
    
    vector<int> ans(n, -1);
    while (!pq.empty()) {
        while (!pq.empty() and ans[pq.top().id] != -1) pq.pop();
        if (pq.empty()) break;
        int bx = cir[pq.top().id].x / R;
        int by = cir[pq.top().id].y / R;
        for (int i : {-2, -1, 0, 1, 2}) {
            for (int j : {-2, -1, 0, 1, 2}) {
                vector<int> tbe;
                for (auto c : cid[{bx + i, by + j}]) {
                    int dx = abs(cir[pq.top().id].x - cir[c].x);
                    int dy = abs(cir[pq.top().id].y - cir[c].y);
                    int dr =     cir[pq.top().id].r + cir[c].r;
                    // cout << dx << " " << dy << " " << dr << "\n";
                    if (dx*dx + dy*dy <= dr*dr) tbe.eb(c), ans[c] = pq.top().id;
                }
                for (auto x : tbe) cid[{bx + i, by + j}].erase(x);
            }
        }
    }
    
    for (int i = 0; i < n; ++i) cout << ans[i] + 1 << " \n"[i == n-1];
    
    return 0;
}

Compilation message

/tmp/ccUnjWlw.o: In function `__gnu_pbds::detail::gp_ht_map<std::pair<long long, long long>, std::set<long long, std::less<long long>, std::allocator<long long> >, std::tr1::hash<std::pair<long long, long long> >, std::equal_to<std::pair<long long, long long> >, std::allocator<char>, false, __gnu_pbds::direct_mask_range_hashing<unsigned long>, __gnu_pbds::linear_probe_fn<unsigned long>, __gnu_pbds::hash_standard_resize_policy<__gnu_pbds::hash_exponential_size_policy<unsigned long>, __gnu_pbds::hash_load_check_resize_trigger<false, unsigned long>, false, unsigned long> >::resize_imp(__gnu_pbds::detail::gp_ht_map<std::pair<long long, long long>, std::set<long long, std::less<long long>, std::allocator<long long> >, std::tr1::hash<std::pair<long long, long long> >, std::equal_to<std::pair<long long, long long> >, std::allocator<char>, false, __gnu_pbds::direct_mask_range_hashing<unsigned long>, __gnu_pbds::linear_probe_fn<unsigned long>, __gnu_pbds::hash_standard_resize_policy<__gnu_pbds::hash_exponential_size_policy<unsigned long>, __gnu_pbds::hash_load_check_resize_trigger<false, unsigned long>, false, unsigned long> >::entry*, unsigned long)':
circle_selection.cpp:(.text._ZN10__gnu_pbds6detail9gp_ht_mapISt4pairIxxESt3setIxSt4lessIxESaIxEENSt3tr14hashIS3_EESt8equal_toIS3_ESaIcELb0ENS_25direct_mask_range_hashingImEENS_15linear_probe_fnImEENS_27hash_standard_resize_policyINS_28hash_exponential_size_policyImEENS_30hash_load_check_resize_triggerILb0EmEELb0EmEEE10resize_impEPNSP_5entryEm[_ZN10__gnu_pbds6detail9gp_ht_mapISt4pairIxxESt3setIxSt4lessIxESaIxEENSt3tr14hashIS3_EESt8equal_toIS3_ESaIcELb0ENS_25direct_mask_range_hashingImEENS_15linear_probe_fnImEENS_27hash_standard_resize_policyINS_28hash_exponential_size_policyImEENS_30hash_load_check_resize_triggerILb0EmEELb0EmEEE10resize_impEPNSP_5entryEm]+0x71): undefined reference to `std::tr1::hash<std::pair<long long, long long> >::operator()(std::pair<long long, long long>) const'
/tmp/ccUnjWlw.o: In function `main':
circle_selection.cpp:(.text.startup+0x4de): undefined reference to `std::tr1::hash<std::pair<long long, long long> >::operator()(std::pair<long long, long long>) const'
circle_selection.cpp:(.text.startup+0x9c1): undefined reference to `std::tr1::hash<std::pair<long long, long long> >::operator()(std::pair<long long, long long>) const'
circle_selection.cpp:(.text.startup+0xcd3): undefined reference to `std::tr1::hash<std::pair<long long, long long> >::operator()(std::pair<long long, long long>) const'
circle_selection.cpp:(.text.startup+0x12e2): undefined reference to `std::tr1::hash<std::pair<long long, long long> >::operator()(std::pair<long long, long long>) const'
/tmp/ccUnjWlw.o:circle_selection.cpp:(.text.startup+0x1942): more undefined references to `std::tr1::hash<std::pair<long long, long long> >::operator()(std::pair<long long, long long>) const' follow
collect2: error: ld returned 1 exit status