Submission #160535

#TimeUsernameProblemLanguageResultExecution timeMemory
160535MinnakhmetovCircle selection (APIO18_circle_selection)C++14
100 / 100
2536 ms54616 KiB
#include <bits/stdc++.h> #define ll long long #define all(aaa) aaa.begin(), aaa.end() using namespace std; struct C { ll x, y, r, i; }; const int N = 3e5 + 5, INF = 1e9; map<pair<ll, ll>, vector<int>> mp; bool used[N]; C cir[N]; int n; int ans[N]; bool check(const C &a, const C &b) { return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) <= (a.r + b.r) * (a.r + b.r); } void build(int r) { mp.clear(); for (int i = 0; i < n; i++) { if (!used[i]) { mp[{cir[i].x / r, cir[i].y / r}].push_back(i); } } } signed main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cin >> n; int cur = 0; for (int i = 0; i < n; i++) { cin >> cir[i].x >> cir[i].y >> cir[i].r; cir[i].x += INF; cir[i].y += INF; cir[i].i = i; } sort(cir, cir + n, [](const C &a, const C &b) { return a.r == b.r ? a.i < b.i : a.r > b.r; }); cur = cir[0].r; build(cur); for (int i = 0; i < n; i++) { if (!used[i]) { // cout << cir[i].x << " " << cir[i].y << " " << cir[i].r << "\n"; if (cir[i].r * 2 < cur) { cur = cir[i].r; build(cur); } int x = cir[i].x / cur, y = cir[i].y / cur; for (int j = x - 2; j <= x + 2; j++) { for (int k = y - 2; k <= y + 2; k++) { if (mp.count({j, k})) { vector<int> &v = mp[{j, k}]; for (int h = 0; h < v.size(); h++) { if (check(cir[i], cir[v[h]])) { ans[cir[v[h]].i] = cir[i].i; used[v[h]] = 1; swap(v.back(), v[h]); v.pop_back(); h--; } } } } } } } for (int i = 0; i < n; i++) { cout << ans[i] + 1 << " "; } return 0; }

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:72:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         for (int h = 0; h < v.size(); h++) {
                                         ~~^~~~~~~~~~
#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...