30分求助
查看原帖
30分求助
681553
Shengzai_楼主2024/7/30 21:30

前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
*/
2024/7/30 21:30
加载中...