제출 #1262923

#제출 시각아이디문제언어결과실행 시간메모리
12629234QT0RCircle selection (APIO18_circle_selection)C++20
7 / 100
3095 ms32916 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long ll n; vector<array<ll, 3>> info; vector<ll> ans; unordered_set<ll> on; ll sq(ll x) { return x * x; } bool query(ll i, ll j) { return (sq(info[i][0] - info[j][0]) + sq(info[i][1] - info[j][1])) <= sq(info[i][2] + info[j][2]); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; ans.resize(n); for (ll i = 1, x, y, r; i <= n; i++) { cin >> x >> y >> r; info.push_back({x, y, r}); on.insert(i-1); } vector<ll> kol(n); iota(kol.begin(), kol.end(), 0); sort(kol.begin(), kol.end(), [&](ll a, ll b) { return info[a][2] == info[b][2] ? a < b : info[a][2] > info[b][2]; }); for (auto now : kol) { if (!on.count(now)) continue; vector<ll> to_remove; for (auto u : on) { if (query(now, u)) { ans[u] = now; to_remove.push_back(u); } } while(to_remove.size()){ on.erase(to_remove.back()); to_remove.pop_back(); } } for (auto x : ans) cout << x + 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...