Submission #103656

#TimeUsernameProblemLanguageResultExecution timeMemory
103656osaaateiasavtnlCircle selection (APIO18_circle_selection)C++14
72 / 100
3040 ms46688 KiB
#include<bits/stdc++.h> using namespace std; #define Point pair <int, int> #define x first #define y second const int N = 3e5 + 7; int n; Point a[N]; int r[N]; int par[N]; int cur = 1 << 30; vector<vector<int>> av; vector<int> px; int per[N]; bool compx(int i, int j) { return a[i].x < a[j].x; } bool compy(int i, int j) { return a[i].y < a[j].y; } bool used[N]; struct Comp { bool operator () (const int i, const int j) { return (r[i] > r[j]) || (r[i] == r[j] && i < j); } }; set <int,Comp> ms; void build() { av.clear(); px.clear(); int ptr = 0; while (ptr < n) { int r = ptr; while (r + 1 < n && a[per[ptr]].x / cur == a[per[r + 1]].x / cur) ++r; av.push_back({}); for (int i = ptr; i <= r; ++i) { av.back().push_back(per[i]); } sort(av.back().begin(), av.back().end(), compy); px.push_back(a[per[ptr]].x / cur); ptr = r + 1; } } bool intersect(int i, int j) { typedef long long ll; return (ll)(a[i].x - a[j].x) * (a[i].x - a[j].x) + (ll)(a[i].y - a[j].y) * (a[i].y - a[j].y) <= (ll)(r[i] + r[j]) * (r[i] + r[j]); } void check(int el, int i) { #ifdef HOME cout << "check " << el + 1 << ' ' << i + 1 << '\n'; #endif if (used[i]) return; if (intersect(el, i)) { used[i] = 1; par[i] = el; ms.erase(i); } } void work(int el, int x, int y) { auto t = lower_bound(px.begin(), px.end(), x); if (*t == x) { int pos = t - px.begin(); #ifdef HOME cout << "work " << el + 1 << ' ' << pos << '\n'; #endif int l = -1, r = av[pos].size(); while (l < r - 1) { int m = (l + r) >> 1; int i = av[pos][m]; if (a[i].y / cur < y) l = m; else r = m; } for (int i = r; i < (int)av[pos].size(); ++i) { if (a[av[pos][i]].y / cur != y) { break; } check(el, av[pos][i]); } } } void print_struct() { for (int i = 0; i < (int)av.size(); ++i) { cout << px[i] << " : "; for (int t : av[i]) cout << t + 1 << ' '; cout << '\n'; } } signed main() { #ifdef HOME freopen("input.txt", "r", stdin); #else ios_base::sync_with_stdio(0); cin.tie(0); #endif cin >> n; for (int i = 0; i < n; ++i) { cin >> a[i].x >> a[i].y >> r[i]; } for (int i = 0; i < n; ++i) { per[i] = i; } sort(per, per + n, compx); for (int i = 0; i < n; ++i) { ms.insert(i); } build(); while (ms.size()) { int i = *ms.begin(); while ((cur >> 1) >= r[i]) { cur >>= 1; build(); } #ifdef HOME cout << "eliminate " << i + 1 << '\n'; cout << "cur " << cur << '\n'; print_struct(); #endif int ix = a[i].x / cur, iy = a[i].y / cur; for (int dx = -2; dx <= 2; ++dx) { for (int dy = -2; dy <= 2; ++dy) { work(i, ix + dx, iy + dy); } } } for (int i = 0; i < n; ++i) { cout << par[i] + 1 << ' '; } cout << '\n'; }
#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...