제출 #771917

#제출 시각아이디문제언어결과실행 시간메모리
771917mcdx9524원 고르기 (APIO18_circle_selection)C++17
19 / 100
738 ms95832 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define int long long struct circle { int x, y, r, index; }; vector <vector <circle> > build_matrix(vector <circle> circles, int sz) { sort(circles.begin(), circles.end(), [](const circle &a, const circle &b) { return a.x < b.x; }); int n = (int) circles.size(); vector <circle> cur; vector <vector <circle> > res; for (int i = 0; i < n; i++) { if (cur.empty() || cur.back().x / sz == circles[i].x / sz) { cur.push_back(circles[i]); } else { res.push_back(cur); cur = {circles[i]}; } } if (!cur.empty()) { res.push_back(cur); } for (auto &to : res) { sort(to.begin(), to.end(), [](const circle &a, const circle &b) { return a.y < b.y; }); } return res; } bool query(const circle &a, const circle &b) { long long distance = (a.x - b.x) * 1ll * (a.x - b.x) + (a.y - b.y) * 1ll * (a.y - b.y); return distance <= (a.r + b.r) * 1ll * (a.r + b.r); } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector <circle> c; set <pair <int, int>, greater <pair <int, int> > > rads; for (int i = 0; i < n; i++) { int x, y, r; cin >> x >> y >> r; c.push_back({x, y, r, i}); rads.insert({r, -i}); } int sz = rads.begin()->first; auto result = build_matrix(c, sz); vector <int> rem(n, -1); for (int i = 0; i < n; i++) { auto it = rads.begin(); int index = -it->second; int cur_rad = it->first; rads.erase(it); if (rem[index] != -1) { continue; } rem[index] = index; if (cur_rad <= sz / 2) { sz /= 2; result = build_matrix(c, sz); } int xl = n, xr = -1; { int starting_point = (c[index].x / sz) * sz; int prev_point = starting_point - 2 * sz; int l = 0, r = (int) result.size() - 1; int res = n; while (l <= r) { int mid = (l + r) / 2; if (result[mid][0].x >= prev_point) { r = mid - 1; res = mid; } else { l = mid + 1; } } xl = res; } { int starting_point = (c[index].x / sz) * sz; int next_point = starting_point + 3 * sz; int l = 0, r = (int) result.size() - 1; int res = n; while (l <= r) { int mid = (l + r) / 2; if (result[mid][0].x >= next_point) { r = mid - 1; res = mid; } else { l = mid + 1; } } xr = res; xr--; } xl = max(0ll, xl); xr = min((int) result.size() - 1, xr); for (int j = xl; j <= xr; j++) { int yl = n, yr = -1; { int starting_point = (c[index].y / sz) * sz; int prev_point = starting_point - 2 * sz; int l = 0, r = (int) result[j].size() - 1; int res = n; while (l <= r) { int mid = (l + r) / 2; if (result[j][mid].y >= prev_point) { r = mid - 1; res = mid; } else { l = mid + 1; } } yl = res; } { int starting_point = (c[index].y / sz) * sz; int next_point = starting_point + 3 * sz; int l = 0, r = (int) result[j].size() - 1; int res = n; while (l <= r) { int mid = (l + r) / 2; if (result[j][mid].y >= next_point) { r = mid - 1; res = mid; } else { l = mid + 1; } } yr = res; yr--; } yl = max(0ll, yl); yr = min((int) result[j].size() - 1, yr); for (int k = yl; k <= yr; k++) { if (rem[result[j][k].index] == -1 && query(c[index], result[j][k])) { rem[result[j][k].index] = index; } } } } for (int i = 0; i < n; i++) { cout << rem[i] + 1 << ' '; } 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...