Submission #1107088

#TimeUsernameProblemLanguageResultExecution timeMemory
1107088mispertionCircle selection (APIO18_circle_selection)C++17
72 / 100
3066 ms99136 KiB
#include<bits/stdc++.h> using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); using ll = long long; #define int ll using ld = long double; using pii = pair<int, int>; #define F first #define S second const ld PI = 3.1415926535; const int N = 5e5 + 2; const int M = 2e6 + 1; int mod = 998244353; const int infi = INT_MAX; const ll infl = LLONG_MAX; int mult(int a, int b) { return a * 1LL * b % mod; } int sum(int a, int b) { if (a + b < 0) return a + b + mod; if (a + b >= mod) return a + b - mod; return a + b; } ll binpow(ll a, ll n) { if (n == 0) return 1; if (n % 2 == 1) { return binpow(a, n - 1) * a % mod; } else { ll b = binpow(a, n / 2); return b * b % mod; } } int n, ans[N]; int csz = 1e9+1; set<pair<pii, pii>> cs; map<pii, vector<pair<pii, pii>>> mp; pii get(int x, int y){ return {floor((ld)x / (ld)csz), floor((ld)y / (ld)csz)}; } bool inter(pair<pii, pii> a, pair<pii, pii> b){ return (((a.S.F - b.S.F) * (a.S.F - b.S.F) + (a.S.S - b.S.S) * (a.S.S - b.S.S)) <= (a.F.F + b.F.F) * (a.F.F + b.F.F)); } void solve() { cin >> n; for(int i = 1; i <= n; i++){ int x, y, r; cin >> x >> y >> r; cs.insert({{r, n - i + 1}, {x, y}}); mp[get(x, y)].push_back({{r, n - i + 1}, {x, y}}); } while(cs.size() > 0){ auto e = *cs.rbegin(); cs.erase(e); if(e.F.F <= csz / 2){ csz = e.F.F; map<pii, vector<pair<pii, pii>>> np; for(auto bl : mp){ for(auto crc : bl.S){ np[get(crc.S.F, crc.S.S)].push_back(crc); } } mp.swap(np); } ans[n - e.F.S + 1] = n - e.F.S + 1; pii bl = get(e.S.F, e.S.S); for(int x = bl.F - 2; x <= bl.F + 2; x++){ for(int y = bl.S - 2; y <= bl.S + 2; y++){ if(mp.find({x, y}) == mp.end()) continue; for(auto crc : mp[{x, y}]){ if(inter(crc, e)){ if(ans[n - crc.F.S + 1] == 0){ ans[n - crc.F.S + 1] = n - e.F.S + 1; cs.erase(crc); } } } } } } for(int i = 1; i <= n; i++) cout << ans[i] << ' '; cout << '\n'; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; //cin >> t; while (t--) { solve(); } 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...