Submission #95395

#TimeUsernameProblemLanguageResultExecution timeMemory
95395pranjalsshCircle selection (APIO18_circle_selection)C++11
45 / 100
1346 ms54776 KiB
/* Simulate process by checking all circles in square of width 4*r. Use a kd-tree for this. */ #pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; #define cerr cout #define F first #define S second #define FOR(i,a,b) for (auto i = (a); i <= (b); ++i) #define NFOR(i,a,b) for(auto i = (a); i >= (b); --i) #define all(x) (x).begin(), (x).end() #define sz(x) int(x.size()) typedef long long ll; typedef pair <int, int> ii; typedef vector <int> vi; const int inf = 1e9 + 7; string to_string(string s) { return '"' + s + '"';} string to_string(char s) { return string(1, s);} string to_string(const char* s) { return to_string((string) s);} string to_string(bool b) { return (b ? "true" : "false");} template <typename A> string to_string(A); template <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";} template <typename A> string to_string(A v) {bool f = 1; string r = "{"; for (const auto &x : v) {if (!f)r += ", "; f = 0; r += to_string(x);} return r + "}";} void debug_out() { cerr << endl; } template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {cerr << " " << to_string(H); debug_out(T...);} #define pr(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) const int N = 3e5 + 10; vi x, y, r; struct node { int l, r, sum, mid; int aid; node(): l(0), r(0), sum(0), mid(0), aid(0) {} }; vector<node> T; vector<vector<int>> A; vi xc, yc; vi par; inline bool intersect(int i, int j) { return (x[i] - x[j]) * 1LL * (x[i] - x[j]) + (y[i] - y[j]) * 1LL * (y[i] - y[j]) <= (r[i] + r[j]) * 1LL * (r[i] + r[j]); } inline int make_node() { T.emplace_back(); return sz(T) - 1; } int build(int no, bool dim, int xl, int xr, int yl, int yr, const vi& ids) { if (ids.empty()) return no; if (no == 0) no = make_node(); bool g = 1; FOR (i, 1, sz(ids) - 1) if (x[ids[i]] != x[ids[0]] or y[ids[i]] != y[ids[0]]) {g = 0; break;} if (g) { T[no].sum = sz(ids); A.emplace_back(ids); T[no].aid = sz(A)-1; return no; } if (dim) { int mid = rand() % (yr-yl) + yl; vi lids, rids; for (int it : ids) { if (y[it] <= yc[mid]) lids.emplace_back(it); else rids.emplace_back(it); } int L = build(0, 0, xl, xr, yl, mid, lids); int R = build(0, 0, xl, xr, mid + 1, yr, rids); T[no].l = L, T[no].r = R; T[no].sum = T[T[no].l].sum + T[T[no].r].sum; T[no].mid = mid; } else { int mid = rand() % (xr-xl) + xl; vi lids, rids; for (int it : ids) { if (x[it] <= xc[mid]) lids.emplace_back(it); else rids.emplace_back(it); } int L = build(0, 1, xl, mid, yl, yr, lids); int R = build(0, 1, mid + 1, xr, yl, yr, rids); T[no].l = L, T[no].r = R; T[no].sum = T[T[no].l].sum + T[T[no].r].sum; T[no].mid = mid; } return no; } int xu, xv, yu, yv, bc; vi rem; void get(int no, bool dim, int xl, int xr, int yl, int yr) { if (T[no].sum == 0) return; if (xr < xu or xl > xv) return; if (yr < yu or yl > yv) return; if (T[no].l == 0 and T[no].r == 0) { for (int it: A[T[no].aid]) if (intersect(it, bc)) { par[it] = bc; rem.emplace_back(it); T[no].sum--; } reverse(all(rem)); vi& a = A[T[no].aid]; int j = 0; FOR (i, 0, sz(a) - 1) { if (rem.empty() or a[i] != rem.back()) { a[j] = a[i]; ++j; } else { rem.pop_back(); } } a.resize(j); rem.clear(); return; } if (dim) { int mid = T[no].mid; get(T[no].l, 0, xl,xr,yl, mid); get(T[no].r, 0, xl, xr, mid+1, yr); T[no].sum = T[T[no].l].sum + T[T[no].r].sum; } else { int mid = T[no].mid; get(T[no].l, 1, xl, mid, yl, yr); get(T[no].r, 1, mid+1, xr, yl, yr); T[no].sum = T[T[no].l].sum + T[T[no].r].sum; } } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; x.resize(n), y.resize(n), r.resize(n); par = vi(n, -1); FOR (i, 0, n - 1) { cin >> x[i] >> y[i] >> r[i]; xc.emplace_back(x[i]); yc.emplace_back(y[i]); } xc.emplace_back(-inf), xc.emplace_back(inf); yc.emplace_back(-inf), yc.emplace_back(inf); sort(all(xc)); xc.erase(unique(all(xc)), xc.end()); sort(all(yc)); yc.erase(unique(all(yc)), yc.end()); vi id(n); iota(all(id), 0); sort(all(id), [&](int x, int y) { if (r[x] == r[y]) return x < y; return r[x] > r[y]; }); T.reserve(2e7); T.emplace_back(); int root = build(0, 0, 0, sz(xc)-1, 0, sz(yc)-1, id); for (int i : id) if (par[i] == -1) { bc = i; xu = max(x[i] - 2LL * r[i], (ll) - inf); xu = lower_bound(all(xc), xu) - xc.begin(); xv = min(x[i] + 2LL * r[i], (ll)inf); xv = upper_bound(all(xc), xv) - xc.begin()-1; yu = max(y[i] - 2LL * r[i], (ll) - 1e9); yu = lower_bound(all(yc), yu) - yc.begin(); yv = min(y[i] + 2LL * r[i], (ll)1e9); yv = upper_bound(all(yc), yv) - yc.begin()-1; get(root, 0, 0, sz(xc)-1, 0, sz(yc)-1); } FOR (i, 0, n - 1) cout << par[i] + 1 << " "; return 0; }
#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...