Submission #107874

#	Time	Username	Problem	Language	Result	Execution time	Memory
107874		kuroni	Circle selection (APIO18_circle_selection)	C++17	100 / 100	2241 ms	43728 KiB

circle_selection

#include <iostream>
#include <cstdio>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

const int N = 300005, MX = 1E9, INF = 2E9 + 7;

int n, cur = INF, ans[N], ind[N];
unordered_map<long long, vector<int>> gri;

long long sqr(long long u)
{
    return u * u;
}

struct SCircle
{
    int x, y, r;

    bool intersect(SCircle oth)
    {
        return sqr(oth.x - x) + sqr(oth.y - y) <= sqr(oth.r + r);
    }
} a[N];

void make_grid(int sz)
{
    gri.clear();
    for (int i = 1; i <= n; i++)
        if (ans[i] == 0)
        {
            int cx = a[i].x / sz, cy = a[i].y / sz;
            long long pos = 1LL * cx * INF + cy;
            gri[pos].push_back(i);
        }
}

void solve(long long pos, int u)
{
    if (gri.count(pos) == 0)
        return;
    vector<int> &cur = gri[pos];
    for (int i = 0; i < cur.size(); i++)
        if (a[cur[i]].intersect(a[u]))
        {
            ans[cur[i]] = u;
            swap(cur[i--], cur.back());
            cur.pop_back();
        }
    if (cur.empty())
        gri.erase(pos);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].r);
        a[i].x += MX; a[i].y += MX;
        ind[i] = i;
    }
    sort(ind + 1, ind + n + 1, [](const int &x, const int &y) {
        return a[x].r > a[y].r || (a[x].r == a[y].r && x < y);
    });
    for (int i = 1; i <= n; i++)
    {
        int u = ind[i];
        if (ans[u] == 0)
        {
            if (a[u].r <= cur / 2)
            {
                cur = a[u].r;
                make_grid(cur);
            }
            for (int cx = a[u].x / cur - 2; cx <= a[u].x / cur + 2; cx++)
                for (int cy = a[u].y / cur - 2; cy <= a[u].y / cur + 2; cy++)
                    solve(1LL * cx * INF + cy, u);
        }
    }
    for (int i = 1; i <= n; i++)
        printf("%d ", ans[i]);
}

Compilation message (stderr)

circle_selection.cpp: In function 'void solve(long long int, int)':
circle_selection.cpp:45:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < cur.size(); i++)
                     ~~^~~~~~~~~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
circle_selection.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].r);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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