Submission #375984

#	Time	Username	Problem	Language	Result	Execution time	Memory
375984		usachevd0	Circle selection (APIO18_circle_selection)	C++14	100 / 100	1431 ms	46596 KiB

circle_selection

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; }
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; }
void debug_out() { cerr << endl; }
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) { cerr << ' ' << A; debug_out(B...); }
template<typename T> void mdebug_out(T* a, int n) { for (int i = 0; i < n; ++i) cerr << a[i] << ' '; cerr << endl; }
#ifdef DEBUG
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
    #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
    #define debug(...) 1337
    #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T> &a) { for (auto &x : a) stream << x; return stream; }
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& a) { return stream << a.fi << ' ' << a.se; }

const int INF32 = 0x3f3f3f3f;
const int maxC = 1e9 + 7;
const int N = 300005;
int n;

ll Floor(ll a, ll b);
ll Ceil(ll a, ll b);
ll Floor(ll a, ll b)
{
    if (b < 0) a = -a, b = -b;
    if (a < 0) return -Ceil(-a, b);
    return a / b;
}
ll Ceil(ll a, ll b)
{
    if (b < 0) a = -a, b = -b;
    if (a < 0) return -Floor(-a, b);
    return a / b + (a % b != 0);
}

struct Circle
{
    int x, y, r;
};
ll sqr(ll x) { return x * x; }
bool intersect(Circle lhs, Circle rhs)
{
    return sqr(lhs.x - rhs.x) + sqr(lhs.y - rhs.y) <= sqr(lhs.r + rhs.r);
}

Circle C[N];
int ord[N], who[N];

int R;
unordered_map<ll, int> compr;
int vtx;
vector<int> grid[N];
int gt(int x, int y, bool bad = false)
{
    x += maxC;
    y += maxC;
    ll key = x * (ll)(2 * maxC) + y;
    if (compr.find(key) == compr.end())
    {
        if (bad) return -1;
        compr.insert(mp(key, vtx));
        return vtx++;
    }
    return compr[key];
}

void Slice(int newR)
{
    compr.clear();
    for (int g = 0; g < vtx; ++g)
        grid[g].clear();
    vtx = 0;

    R = newR;
    for (int i = 1; i <= n; ++i) if (!who[i])
    {
        int x = Floor(C[i].x, R);
        int y = Floor(C[i].y, R);
        int g = gt(x, y);
        grid[g].push_back(i);
    }
}

signed main()
{
#ifdef DEBUG
    freopen("in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> C[i].x >> C[i].y >> C[i].r;
    }
    iota(ord, ord + n, 1);
    sort(ord, ord + n, [&](int i, int j) -> bool
    {
        if (C[i].r != C[j].r)
            return C[i].r > C[j].r;
        return i < j;
    });
    R = 2 * INF32;
    for (int t = 0; t < n; ++t)
    {
        int i = ord[t];
        if (who[i]) continue;
        if (C[i].r * 2 <= R) Slice(C[i].r);
        int X = Floor(C[i].x, R);
        int Y = Floor(C[i].y, R);
        for (int x = X - 2; x <= X + 2; ++x)
            for (int y = Y - 2; y <= Y + 2; ++y)
            {
                int g = gt(x, y, true);
                if (g == -1) continue;
                vector<int> new_grid;
                for (int j : grid[g])
                {
                    if (!who[j] && intersect(C[i], C[j]))
                        who[j] = i;
                    else
                        new_grid.push_back(j);
                }
                swap(grid[g], new_grid);
            }
    }
    for (int i = 1; i <= n; ++i)
        cout << who[i] << ' ';
    cout << '\n';

    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