| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 811256 | CYMario | 원 고르기 (APIO18_circle_selection) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <stdio.h>
#include <algorithm>
#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(' ');
}