Submission #450360

#	Time	Username	Problem	Language	Result	Execution time	Memory
450360		ymm	Circle selection (APIO18_circle_selection)	C++17	100 / 100	2107 ms	54920 KiB

circle_selection

///
///    I have a dream and a piano
///

#pragma GCC optimize("O3,unroll-loops")

#define _USE_MATH_DEFINES
#define FAST ios::sync_with_stdio(false),cin.tie(0);
#include <bits/stdc++.h>
#define Loop(x, l, r) for(int x = (l); x < (r); ++x)
#define LoopR(x, l, r) for(int x = (r)-1; x >= (l); --x)
#define all(x) x.begin(), x.end()
#define Kill(x) exit((cout << (x) << '\n', 0))
#define YN(flag) ((flag)? "YES": "NO")
#define F first
#define S second
typedef          long long   ll;
typedef unsigned long long  ull;
typedef std::pair<int,int>  pii;
typedef std::pair<ll ,ll >  pll;
using namespace std;

const int N = 300'010;
ll r[N], x[N], y[N];

inline ll sqr(ll x){return x*x;}
inline bool g(int i, int j){return sqr(x[i]-x[j]) + sqr(y[i]-y[j]) <= sqr(r[i]+r[j]);}

map<pii, vector<pii>> mp[32];
int ans[N];
pll circ[N];
int n;

int main()
{
    FAST;
    cin >> n;
    Loop(i,0,n)
    {
        cin >> x[i] >> y[i] >> r[i];
        x[i] += 1e9; y[i] += 1e9;
        circ[i] = {~r[i], i};
    }
    sort(circ, circ+n);
    Loop(_,0,n)
    {
        int i = circ[_].S;
        int lg = r[i]==1?0:32-__builtin_clz(r[i]-1);
        int mn = 1e9;
        for(int k = lg; k < 32; ++k)
        {
            ll r = k? 1<<(k-1): 0;
            ll d = r? 2*r: 1;
            // (r, d]
            Loop(xx,-1,2) Loop(yy,-1,2){
                auto tmp = mp[k].find(pii{x[i]/(2*d)+xx, y[i]/(2*d)+yy});
                if(tmp == mp[k].end()) continue;
                for(auto [j1, j2] : tmp->S){
                    if(g(i,j2)){
                        mn = min(j1, mn);
                        break;
                    }
                }
            }
        }
        if(mn == 1e9){
            ll r = lg? 1<<(lg-1): 0;
            ll d = r? 2*r: 1;
            mp[lg][pll{x[i]/(2*d), y[i]/(2*d)}].emplace_back(_, i);
            ans[i] = i;
        } else ans[i] = circ[mn].S;
    }
    Loop(i,0,n) cout << ans[i]+1 << ' ';
}

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