Submission #1183227

#TimeUsernameProblemLanguageResultExecution timeMemory
1183227anmattroi원 고르기 (APIO18_circle_selection)C++17
100 / 100
733 ms60932 KiB
#include <bits/stdc++.h> #define maxn 300005 #define fi first #define se second using namespace std; using ii = pair<int, int>; int n, last = 0; int ans[maxn]; struct circle { int x, y, r; } a[maxn]; int intersect(int x, int y) { return (1LL * (a[x].x - a[y].x) * (a[x].x - a[y].x) + 1LL * (a[x].y - a[y].y) * (a[x].y - a[y].y)) <= (1LL * (a[x].r + a[y].r) * (a[x].r + a[y].r)); } namespace getNextCircleHelper { struct evilAndIntimidatingSet { int radius, index; evilAndIntimidatingSet() {} evilAndIntimidatingSet(int _radius, int _index) : radius(_radius), index(_index) {} bool operator < (const evilAndIntimidatingSet &other) const { if (radius != other.radius) return radius > other.radius; return index < other.index; } }; set<evilAndIntimidatingSet> s; void init() { for (int i = 1; i <= n; i++) s.insert(evilAndIntimidatingSet(a[i].r, i)); } } int getNextCircle() { if (getNextCircleHelper::s.empty()) return -1; return getNextCircleHelper::s.begin()->index; } void del(int elimd, int elim) { if (intersect(elimd, elim)) { getNextCircleHelper::s.erase(getNextCircleHelper::evilAndIntimidatingSet(a[elimd].r, elimd)); ans[elimd] = elim; } } int c[maxn], n1 = 0; vector<vector<ii> > rem; vector<vector<int> > nex; ii sortX[maxn], sortY[maxn]; int equivalenceClass[maxn]; int getNext(int i, int j) { return nex[i][j] == j ? j : nex[i][j] = getNext(i, nex[i][j]); } void rebuild(int newRadius) { n1 = 0; last = newRadius; for (int i = 1; i <= n; i++) if (ans[sortX[i].se] == 0) c[++n1] = sortX[i].fi/last; n1 = unique(c + 1, c + n1 + 1) - c - 1; for (int i = 1, it = 1; i <= n; i++) { if (ans[sortX[i].se] > 0) continue; while (it <= n1 && c[it] < sortX[i].fi/last) ++it; equivalenceClass[sortX[i].se] = it; } rem.clear(); nex.clear(); rem.resize(n1+1); nex.resize(n1+1); for (int i = 1; i <= n; i++) if (ans[sortY[i].se] == 0) rem[equivalenceClass[sortY[i].se]].emplace_back(sortY[i].fi/last, sortY[i].se); for (int i = 1; i <= n1; i++) { int sz = rem[i].size(); nex[i].resize(sz+1); iota(nex[i].begin(), nex[i].end(), 0); } } int main() { // freopen("chess.inp", "r", stdin); ios::sync_with_stdio(false); cin.tie(NULL); cin >> n; for (int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y >> a[i].r; for (int i = 1; i <= n; i++) { a[i].x += 1'000'000'000; a[i].y += 1'000'000'000; } for (int i = 1; i <= n; i++) sortX[i] = {a[i].x, i}; for (int i = 1; i <= n; i++) sortY[i] = {a[i].y, i}; sort(sortX + 1, sortX + n + 1); sort(sortY + 1, sortY + n + 1); getNextCircleHelper::init(); for (int i = 1; i <= n; i++) last = max(last, a[i].r); rebuild(last); int numberOfIterations = 0; while (1) { // assert(++numberOfIterations <= n+1); int cur = getNextCircle(); if (cur == -1) break; if (last > a[cur].r * 2) rebuild(a[cur].r); int curX = a[cur].x/last, curY = a[cur].y/last; int stX = lower_bound(c + 1, c + n1 + 1, curX-2) - c; for (int i = stX; i <= n1 && c[i] <= curX+2; i++) { vector<ii> &curVector = rem[i]; int stY = lower_bound(curVector.begin(), curVector.end(), ii{curY-2, 0}) - curVector.begin(); for (int j = stY; j < curVector.size() && curVector[j].fi <= curY+2; j = getNext(i, j+1)) { if (ans[curVector[j].se] > 0) continue; del(curVector[j].se, cur); if (ans[curVector[j].se] == cur) nex[i][j] = j+1; } } } for (int i = 1; i <= n; i++) cout << ans[i] << ' '; } /* 3 29 1 37 93 14 22 74 66 30 */
#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...