Submission #1107106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107106		mispertion	Circle selection (APIO18_circle_selection)	C++17	100 / 100	2752 ms	86436 KiB

circle_selection

#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], x[N], y[N], r[N];
int csz = 1e9+1;
set<pair<pii, pii>> cs;
vector<pii> sps;
vector<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++){
        cin >> x[i] >> y[i] >> r[i];
        cs.insert({{r[i], n - i + 1}, {x[i], y[i]}});
        sps.push_back(get(x[i], y[i]));
    }
    sort(sps.begin(), sps.end());
    sps.resize(unique(sps.begin(), sps.end()) - sps.begin());
    mp.resize(sps.size());
    for(int i = 1; i <= n; i++){
        mp[lower_bound(sps.begin(), sps.end(), get(x[i], y[i])) - sps.begin()].push_back({{r[i], n - i + 1}, {x[i], y[i]}});
    }
    while(cs.size() > 0){
        auto e = *cs.rbegin();
        cs.erase(e);
        if(e.F.F <= csz / 2){
            csz = e.F.F;
            sps.clear();
            for(auto e : mp){
                for(auto crc : e){
                    sps.push_back(get(crc.S.F, crc.S.S));
                }
            }
            sort(sps.begin(), sps.end());
            sps.resize(unique(sps.begin(), sps.end()) - sps.begin());
            mp.assign(sps.size(), vector<pair<pii, pii>>());
            for(int i = 1; i <= n; i++){
                if(ans[i] == 0){
                    mp[lower_bound(sps.begin(), sps.end(), get(x[i], y[i])) - sps.begin()].push_back({{r[i], n - i + 1}, {x[i], y[i]}});
                }
            }
        }        
        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++){
                auto ps = lower_bound(sps.begin(), sps.end(), make_pair(x, y));
                if(ps == sps.end() || *ps != make_pair(x, y))
                    continue;
                for(auto crc : mp[ps - sps.begin()]){
                    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;
}

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 30 / 30
• Subtask 6: 13 / 13