제출 #404789

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
404789		jjang36524	원 고르기 (APIO18_circle_selection)	C++14	49 / 100	3084 ms	42856 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;
pair<int, int>po[300100];
vector<pair<int, int>>so;
int pre[300100];
int num[300100];
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.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]={ a,b };
	}
	sort(so.begin(), so.end());
	int gr = 30;
	for (i = 0; i < N; i++)
	{
		x[po[i].first / (1LL << gr)*(1LL<<31)+ po[i].second / (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++)
			{
				x[po[i].first / (1LL << gr) * (1LL << 31) + po[i].second / (1LL << gr)].push_back(i);
			}
		}
		int xx = po[so[i].second].first / (1LL << gr);
		int y = po[so[i].second].second / (1LL << gr);
		int j, k;
		for (j = xx - 2; j <= xx + 2; j++)
		{
			for (k = y - 2; k <= y + 2; k++)
			{
				if (!x.count(j * (1LL << 31) + k))
					continue;
				int l;
				for (l = 0; l < x[j*(1LL<<31)+ k].size(); l++)
				{
					int le = x[j * (1LL << 31)+ k][l];
					if (num[le])
						continue;
					if ((po[so[i].second].first - po[le].first) * (po[so[i].second].first - po[le].first) + (po[so[i].second].second - po[le].second) * (po[so[i].second].second - po[le].second) <= (-so[i].first + pre[le]) * (-so[i].first + pre[le]))
					{
						num[le] = so[i].second+1;
					}
				}
			}
		}
	}
	for (i = 0; i < N; i++)
	{
		cout << num[i] << ' ';
	}
}

컴파일 시 표준 에러 (stderr) 메시지

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:59:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (l = 0; l < x[j*(1LL<<31)+ k].size(); l++)
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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