제출 #625125

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
625125		jjang36524	원 고르기 (APIO18_circle_selection)	C++14	64 / 100	3102 ms	43000 KiB

circle_selection

#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] << ' ';
	}
}

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