| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 902368 | 2024-01-10T10:26:27 Z | Trisanu_Das | 원 고르기 (APIO18_circle_selection) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long int64_t;
typedef pair<int64_t, int64_t> pii;
const int64_t maxn = 3e5 + 3;
const int64_t inf = 1ll << 60;
const int64_t bl = 2e9 + 3;
struct C {
int64_t x, y, r, id;
};
int64_t n, res[maxn];
bitset<maxn> rmv;
unordered_map<int64_t, vector<int64_t>> mp;
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
cin >> n;
C a[maxn];
for (int64_t i = 0; i < n; ++i) cin >> a[i].x >> a[i].y >> a[i].r, a[i].id = i;
stable_sort(a, a + n, [](const C &x, const C &y) { return x.r > y.r; });
int64_t k = inf;
for (int64_t i = 0; i < n; ++i) {
if (rmv[i]) continue;
if (2 * a[i].r < k) {
k = a[i].r;
mp.clear();
for (int64_t j = i; j < n; ++j) if (!rmv[j]) mp[a[j].x / k * bl + a[j].y / k].push_back(j);
}
int64_t xx = a[i].x / k, yy = a[i].y / k;
for (int64_t x = xx - 2; x <= xx + 2; ++x)
for (int64_t y = yy - 2; y <= yy + 2; ++y) {
auto &tls = mp[x * bl + y];
for (auto it = tls.begin(); it != tls.end(); ++it) {
if (!rmv[*it] && (a[i].x - a[*it].x) * (a[i].x - a[*it].x) + (a[i].y - a[*it].y) * (a[i].y - a[*it].y) <= (a[i].r + a[*it].r) * (a[i].r + a[*it].r)) {
res[a[*it].id] = a[i].id;
rmv[*it] = 1;
}
}
}
}
for (int64_t i = 0; i < n; ++i) cout << res[i] + 1 << " ";
}