제출 #1205619

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1205619		12345678	Circle selection (APIO18_circle_selection)	C++17	100 / 100	823 ms	63272 KiB

circle_selection

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll nx=3e5+5, inf=1e18, cns=1e9;

ll n, x[nx], y[nx], r[nx], res[nx], scaling=inf;
set<pair<ll, ll>> s;
map<ll, vector<pair<ll, ll>>> mp;

void rescale()
{
    mp.clear();
    for (int i=1; i<=n; i++) if (!res[i]) mp[x[i]/scaling].push_back({y[i]/scaling, i});
    for (auto &[x, y]:mp) sort(y.begin(), y.end());
}

void solve()
{
    auto cur=*prev(s.end());
    int idx=-cur.second;
    if (2*cur.first<=scaling) scaling=cur.first, rescale();
    for (auto itr=mp.lower_bound(x[idx]/scaling-2); itr!=mp.end()&&abs(itr->first-x[idx]/scaling)<=2; itr++)
    {
        for (auto itry=lower_bound(itr->second.begin(), itr->second.end(), make_pair(y[idx]/scaling-2, 0ll)); itry!=itr->second.end()&&abs(itry->first-y[idx]/scaling)<=2; itry++)
        {
            int idx2=itry->second;
            if (res[idx2]) continue;
            if ((x[idx]-x[idx2])*(x[idx]-x[idx2])+(y[idx]-y[idx2])*(y[idx]-y[idx2])<=(r[idx]+r[idx2])*(r[idx]+r[idx2]))
            {
                res[idx2]=idx;
                s.erase({r[idx2], -idx2});
            }
        }
    }
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>x[i]>>y[i]>>r[i], x[i]+=cns, y[i]+=cns, s.insert({r[i], -i});
    while (!s.empty()) solve();
    for (int i=1; i<=n; i++) cout<<res[i]<<' ';
}

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