Submission #811257

#	Time	Username	Problem	Language	Result	Execution time	Memory
811257		CYMario	Circle selection (APIO18_circle_selection)	C++17	100 / 100	717 ms	40972 KiB

circle_selection

#include <stdio.h>
#include <algorithm>
#include <list>
#include <unordered_map>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
using namespace std;
typedef long long i64;
int rd()
{
    int k = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        k = (k << 1) + (k << 3) + (c ^ 48);
        c = getchar();
    }
    return f == 1 ? k : -k;
}
void wr(int x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        wr(x / 10);
    putchar((x % 10) ^ '0');
}
const int maxn = 300010;
struct point
{
    int x, y;
    point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
    bool operator< (const point& o) const { return (x ^ o.x) ? x < o.x : y < o.y; }
    bool operator==(const point& o) const { return (x == o.x) && (y == o.y); }
};
struct point_hash
{
    size_t operator()(const point &a) const { return hash<int>()(a.x) * 611953 + hash<int>()(a.y) * 7919; }
};
struct circle
{
    point c;
    int r;
} c[maxn];
int n, idx[maxn], ans[maxn];
bool cmp(int a, int b) 
{
    if (c[a].r ^ c[b].r)
        return c[a].r > c[b].r;
    else
        return a < b;
}
unordered_map<point, list<int>, point_hash> mp;
int grid_r;
void build(int r)
{
    grid_r = r;
    mp.clear();
    for (int i = 1; i <= n; ++i)
        if (!ans[i])
            mp[point((c[i].c.x) / grid_r, (c[i].c.y) / grid_r)].push_back(i);
}
bool check(int i, int j)
{
    i64 dis = 1ll * (c[i].c.x - c[j].c.x) * (c[i].c.x - c[j].c.x) + 1ll * (c[i].c.y - c[j].c.y) * (c[i].c.y - c[j].c.y);
    return dis <= 1ll * (c[i].r + c[j].r) * (c[i].r + c[j].r);
}
int main()
{
    n = rd();
    for (int i = 1; i <= n; ++i)
        c[i].c.x = rd(), c[i].c.y = rd(), c[i].r = rd();
    for (int i = 1; i <= n; ++i)
        idx[i] = i;
    sort(idx + 1, idx + n + 1, cmp);
    build(c[idx[1]].r << 1);
    for (int i = 1; i <= n; ++i)
    {
        if (ans[idx[i]])
            continue;
        if ((i64)grid_r > ((i64)(c[idx[i]].r) << 2))
            build(c[idx[i]].r << 1);
        int x = (c[idx[i]].c.x) / grid_r, y = (c[idx[i]].c.y) / grid_r;
        for (int dx = -1; dx <= 1; ++dx)
            for (int dy = -1; dy <= 1; ++dy)
            {
                point pt = point(x + dx, y + dy);
                if (!mp.count(pt))
                    continue;
                list<int>& it = mp[pt];
                for (list<int>::iterator itt = it.begin(); itt != it.end(); )
                {
                    if (check(idx[i], *itt))
                        ans[*itt] = idx[i], it.erase(itt++);
                    else
                        ++itt;
                }
            }
    }
    for (int i = 1; i <= n; ++i)
        wr(ans[i]), putchar(' ');
}

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