Submission #1263497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263497		Roupiq	Circle selection (APIO18_circle_selection)	C++20	15 / 100	3110 ms	1004684 KiB

circle_selection

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

// ===== precyzyjne liczenie odległości (bez overflow) =====
static inline __int128 sq128(long long v){ return (__int128)v * v; }
static inline bool circles_intersect(long long x1,long long y1,long long r1,
                                     long long x2,long long y2,long long r2){
    __int128 dx = (__int128)x1 - x2;
    __int128 dy = (__int128)y1 - y2;
    __int128 dist2 = dx*dx + dy*dy;
    __int128 sr = (__int128)r1 + r2;
    return dist2 <= sr*sr;
}

struct Circle {
    long long x, y, r;
    int id; // 0..n-1
};

// ===== Spatial Hash (siatka) =====
struct SpatialHash {
    long long S; // rozmiar boku komórki
    // klucz komórki: 64-bit (łączymy (cx, cy))
    struct Key {
        long long cx, cy;
        bool operator==(const Key& o) const { return cx==o.cx && cy==o.cy; }
    };
    struct KeyHash {
        size_t operator()(const Key& k) const {
            // mix 64-bitów
            uint64_t x = std::hash<long long>()(k.cx);
            uint64_t y = std::hash<long long>()(k.cy);
            // splitmix64
            auto mix = [](uint64_t z){
                z += 0x9e3779b97f4a7c15ULL;
                z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL;
                z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL;
                return z ^ (z >> 31);
            };
            return (size_t)(mix(x) ^ (mix(y)<<1));
        }
    };

    // w każdej komórce trzymamy zbiór id kół
    unordered_map<Key, unordered_set<int>, KeyHash> cell2ids;

    // dla szybkiego kasowania: dla każdego koła lista komórek, w których siedzi
    vector<vector<Key>> id_cells;

    SpatialHash() : S(1) {}

    // iloraz podłogi dla liczb ujemnych
    static inline long long floordiv(long long a, long long b){
        // b > 0
        if (a >= 0) return a / b;
        return - ( ( -a + b - 1 ) / b );
    }

    inline Key key_of_point(long long x, long long y) const {
        return { floordiv(x, S), floordiv(y, S) };
    }

    // dodaj koło do wszystkich komórek przecinanych przez jego bbox
    void add_circle(const Circle& c, int id){
        long long xl = c.x - c.r, xr = c.x + c.r;
        long long yl = c.y - c.r, yr = c.y + c.r;
        long long cx1 = floordiv(xl, S), cx2 = floordiv(xr, S);
        long long cy1 = floordiv(yl, S), cy2 = floordiv(yr, S);
        vector<Key> keys;
        keys.reserve((cx2-cx1+1) * (cy2-cy1+1));
        for(long long cx = cx1; cx <= cx2; ++cx){
            for(long long cy = cy1; cy <= cy2; ++cy){
                Key k{cx, cy};
                cell2ids[k].insert(id);
                keys.push_back(k);
            }
        }
        id_cells[id] = std::move(keys);
    }

    // usuń koło ze wszystkich wcześniej zapamiętanych komórek
    void remove_circle(int id){
        for(const Key& k : id_cells[id]){
            auto it = cell2ids.find(k);
            if(it != cell2ids.end()){
                it->second.erase(id);
                if(it->second.empty()) cell2ids.erase(it);
            }
        }
        id_cells[id].clear();
    }

    // zwraca unikalnych kandydatów z komórek bbox zapytania
    template<class FnPush>
    void for_candidates_bbox(long long xl, long long yl, long long xr, long long yr, FnPush push){
        long long cx1 = floordiv(xl, S), cx2 = floordiv(xr, S);
        long long cy1 = floordiv(yl, S), cy2 = floordiv(yr, S);
        for(long long cx = cx1; cx <= cx2; ++cx){
            for(long long cy = cy1; cy <= cy2; ++cy){
                Key k{cx, cy};
                auto it = cell2ids.find(k);
                if(it == cell2ids.end()) continue;
                for(int id : it->second) push(id);
            }
        }
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if(!(cin >> n)) return 0;
    vector<Circle> a(n);
    long long minx=LLONG_MAX, maxx=LLONG_MIN, miny=LLONG_MAX, maxy=LLONG_MIN;
    for(int i=0;i<n;i++){
        cin >> a[i].x >> a[i].y >> a[i].r;
        a[i].id = i;
        minx = min(minx, a[i].x);
        maxx = max(maxx, a[i].x);
        miny = min(miny, a[i].y);
        maxy = max(maxy, a[i].y);
    }

    // Porządek wyboru: malejąco po r, przy remisie rosnąco po id
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j){
        if(a[i].r != a[j].r) return a[i].r > a[j].r;
        return i < j;
    });

    // Dobór rozmiaru komórki S ~ (rozpiętość / sqrt(n)), min 1
    long long spanx = maxx - minx + 1;
    long long spany = maxy - miny + 1;
    long double avgspan = (long double)spanx + (long double)spany;
    long double rootn = max(1.0L, sqrtl((long double)max(1, n)));
    long long S = (long long) max(1.0L, (avgspan / 2.0L) / rootn);

    SpatialHash grid;
    grid.S = S;
    grid.id_cells.assign(n, {});

    vector<char> alive(n, 1);
    vector<int> killer(n, -1);

    // wstaw wszystkie koła do siatki
    for(int i=0;i<n;i++){
        grid.add_circle(a[i], i);
    }

    // iterujemy w porządku wyboru
    vector<char> seen_flag(n, 0); // do odszumienia kandydatów (unikaty)
    vector<int> candidates_buf; candidates_buf.reserve(1024);

    for(int idx : order){
        if(!alive[idx]) continue; // już usunięte wcześniej
        // to koło zostaje WYBRANE i zabija siebie i sąsiadów-kolidujących
        // najpierw zbierz kandydatów z bbox
        long long xl = a[idx].x - a[idx].r;
        long long xr = a[idx].x + a[idx].r;
        long long yl = a[idx].y - a[idx].r;
        long long yr = a[idx].y + a[idx].r;

        candidates_buf.clear();
        grid.for_candidates_bbox(xl, yl, xr, yr, [&](int j){
            if(!seen_flag[j]){
                seen_flag[j] = 1;
                candidates_buf.push_back(j);
            }
        });

        // sam wybrany też ma wynik = on sam
        killer[idx] = idx + 1; // 1-based w odpowiedzi
        alive[idx] = 0;
        grid.remove_circle(idx);

        // sprawdź kandydatów i usuń kolidujących, którzy nadal żyją
        for(int j : candidates_buf){
            seen_flag[j] = 0; // od razu czyścimy flagę
            if(j == idx) continue;
            if(!alive[j]) continue;
            if(circles_intersect(a[idx].x, a[idx].y, a[idx].r,
                                 a[j].x,  a[j].y,  a[j].r)){
                killer[j] = idx + 1;
                alive[j] = 0;
                grid.remove_circle(j);
            }
        }
    }

    // koła, które nigdy nie zostały „złapane” przez większe (np. samotne),
    // muszą mieć killer ustawiony na siebie (zostają wybrane, gdy przyjdzie ich kolej)
    for(int i=0;i<n;i++){
        if(killer[i] < 0) killer[i] = i + 1;
    }

    for(int i=0;i<n;i++){
        if(i) cout << ' ';
        cout << killer[i];
    }
    cout << '\n';
    return 0;
}

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