This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <experimental/random>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #include <windows.h>
// #pragma comment(lib, "shell32")
// ShellExecute(0, "open", your_url, NULL, NULL, SW_SHOWDEFAULT)
using namespace std;
using namespace __gnu_pbds;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
const int MOD = 998244353;
const int INF = 1e9;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
void solve();
signed main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int qwerty = 1;
// cin >> qwerty;
while (qwerty--) {
solve();
}
}
struct circle {
int x, y, r, ind;
};
bool cmp(circle a, circle b) {
return a.r > b.r || (a.r == b.r && a.ind < b.ind);
}
bool per(circle a, circle b) {
return 1ll * (a.x - b.x) * (a.x - b.x) + 1ll * (a.y - b.y) * (a.y - b.y) <= 1ll * (a.r + b.r) * (a.r + b.r);
}
void solve() {
int n;
cin >> n;
vector<circle> cs(n);
for (int i = 0; i < n; i++) {
cin >> cs[i].x >> cs[i].y >> cs[i].r;
cs[i].ind = i;
}
sort(cs.begin(), cs.end(), cmp);
vector<int> ans(n, -1);
for (int for_r = 30; for_r >= 0; for_r--) {
int r = (1 << for_r);
map<pair<int, int>, vector<int>> mp;
bool flag = false;
for (int i = 0; i < n; ++i) {
if (ans[cs[i].ind] == -1 && cs[i].r >= r / 2 && cs[i].r <= r) {
flag = true;
break;
}
}
if (!flag) continue;
for (int i = 0; i < n; i++) {
if (ans[cs[i].ind] == -1) {
mp[{cs[i].x / r, cs[i].y / r}].push_back(i);
}
}
for (int i = 0; i < n; i++) {
if (cs[i].r < r / 2) break;
if (cs[i].r > r || ans[cs[i].ind] != -1) continue;
for (int x = cs[i].x / r - 2; x <= cs[i].x / r + 2; x++) {
for (int y = cs[i].y / r - 2; y <= cs[i].y / r + 2; y++) {
vector<int> &now = mp[{x, y}];
for (int j = (int) now.size() - 1; j >= 0; j--) {
int jj = now[j];
if (per(cs[i], cs[jj])) {
ans[cs[jj].ind] = cs[i].ind;
swap(now[j], now.back());
now.pop_back();
}
}
}
}
}
}
for (int i: ans) {
cout << i + 1 << ' ';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |