답안 #404791

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
404791	2021-05-15T02:36:33 Z	jjang36524	원 고르기 (APIO18_circle_selection)	C++14	컴파일 오류	0 ms	0 KB

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);
	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++)
			{
				x[po[i][0] / (1LL << gr) * (1LL << 31) + po[i][1] / (1LL << gr)].push_back(i);
			}
		}
		int xx = po[so[i].second][0] / (1LL << gr);
		int y = po[so[i].second][1] / (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;
					int xxx = (po[so[i].second][0] - po[le][0]);
					int yyy = (po[so[i].second][1] - po[le][1]);
					int rrr= (-so[i].first + pre[le])
					if (xxx*xxx+yyy*yyy<=rrr*rrr)
					{
						num[le] = so[i].second+1;
					}
				}
			}
		}
	}
	for (i = 0; i < N; i++)
	{
		cout << num[i] << ' ';
	}
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:60: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]
   60 |     for (l = 0; l < x[j*(1LL<<31)+ k].size(); l++)
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:68:6: error: expected ',' or ';' before 'if'
   68 |      if (xxx*xxx+yyy*yyy<=rrr*rrr)
      |      ^~
circle_selection.cpp:65:10: warning: unused variable 'xxx' [-Wunused-variable]
   65 |      int xxx = (po[so[i].second][0] - po[le][0]);
      |          ^~~
circle_selection.cpp:66:10: warning: unused variable 'yyy' [-Wunused-variable]
   66 |      int yyy = (po[so[i].second][1] - po[le][1]);
      |          ^~~
circle_selection.cpp:67:10: warning: unused variable 'rrr' [-Wunused-variable]
   67 |      int rrr= (-so[i].first + pre[le])
      |          ^~~