Submission #1263497

#TimeUsernameProblemLanguageResultExecution timeMemory
1263497Roupiq원 고르기 (APIO18_circle_selection)C++20
15 / 100
3110 ms1004684 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...