前3个点正确,后面的全wa,输出均比正确答案小,麻烦大佬帮忙看一下,谢谢
#include <bits/stdc++.h>
#define int long long
#define L(x) (x - 1) * siz + 1
#define R(x) min(x * siz, n)
using namespace std;
const int N = 2500100;
struct magnet
{
int x, y, m, p, r, tag;
} a[N];
int n, siz, num;
int pos[N], pre[5100], mx[5100];
int D(int x, int y)
{
return (x - a[0].x) * (x - a[0].x) + (y - a[0].y) * (y - a[0].y);
}
bool cmp1(magnet u, magnet v)
{
return D(u.x, u.y) < D(v.x, v.y);
}
bool cmp2(magnet u, magnet v)
{
return u.m < v.m;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
//read
cin >> a[0].x >> a[0].y >> a[0].p >> a[0].r >> n;
for (int i = 1; i <= n; i++)
cin >> a[i].x >> a[i].y >> a[i].m >> a[i].p >> a[i].r;
//build
sort(a + 1, a + n + 1, cmp1);
siz = sqrt(n);
num = (n - 1) / siz + 1;
for (int i = 1; i <= n; i++) pos[i] = (i - 1) / siz + 1;
for (int i = 1; i <= num; i++)
{
mx[i] = D(a[R(i)].x, a[R(i)].y);
pre[i] = L(i);
sort(a + L(i), a + R(i) + 1, cmp2);
}
//bfs
int ans = 0;
queue<magnet> q;
q.push(a[0]);
while (!q.empty())
{
magnet u = q.front();
q.pop();
for (int i = 1; i <= num; i++)
if (mx[i] <= u.r * u.r)
for (int& j = pre[i]; j <= R(i) && u.p >= a[j].m; j++)
if (!a[j].tag)
q.push(a[j]), a[j].tag = 1, ans++;
else
{
for (int j = L(i); j <= R(i); j++)
if (D(a[j].x, a[j].y) <= u.r * u.r && u.p >= a[j].m && !a[j].tag)
q.push(a[j]), a[j].tag = 1, ans++;
break;
}
}
cout << ans;
return 0;
}
/*
0 0 5 10 5
5 4 7 11 5
-7 1 4 7 8
0 2 13 5 6
2 -3 9 3 4
13 5 1 9 9
*/