이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
#define int long long
using namespace std;
unordered_map<int, vector<int>>x;
int po[300100][2];
vector<pair<int, int>>so;
int pre[300100];
int num[300100];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
int i;
for (i = 0; i < N; i++)
{
int a, b, c;
cin >> a >> b >> c;
a += 1LL << 30;
b += 1LL << 30;
pre[i] = c;
so.push_back({ -c,i });
po[i][0] = a;
po[i][1] = b;
}
sort(so.begin(), so.end());
int gr = 30;
for (i = 0; i < N; i++)
{
x[po[i][0] / (1LL << gr) * (1LL << 31) + po[i][1] / (1LL << gr)].push_back(i);
}
for (i = 0; i < N; i++)
{
if (num[so[i].second])
continue;
while ((1LL << gr) >= -so[i].first * 2)
{
gr--;
x.clear();
int i;
for (i = 0; i < N; i++)
{
if (num[i])
continue;
x[po[i][0] / (1LL << gr) * (1LL << 31) + po[i][1] / (1LL << gr)].push_back(i);
}
}
int cuuu = so[i].second;
int xx = po[cuuu][0] / (1LL << gr);
int y = po[cuuu][1] / (1LL << gr);
int j, k;
for (j = xx - 2; j <= xx + 2; j++)
{
for (k = y - 2; k <= y + 2; k++)
{
int v=(j<<31)+k;
if (!x.count(j * (1LL << 31) + k))
continue;
for (auto l = x[v].begin(); l != x[v].end(); l++)
{
int le = *l;
if (num[le])
continue;
int xxx = (po[cuuu][0] - po[le][0]);
int yyy = (po[cuuu][1] - po[le][1]);
int rrr = (-so[i].first + pre[le]);
if (xxx * xxx + yyy * yyy <= rrr * rrr)
{
num[le] = cuuu + 1;
}
}
}
}
}
for (i = 0; i < N; i++)
{
cout << num[i] << ' ';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |