제출 #64363

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
64363		zscoder	원 고르기 (APIO18_circle_selection)	C++17	7 / 100	3044 ms	51156 KiB

circle_selection

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

struct circle
{
	int x,y,r,id;
	circle(int _x, int _y, int _r, int _id){x=_x;y=_y;r=_r;id=_id;}
};

bool operator<(circle a, circle b)
{
	if(a.r!=b.r) return a.r<b.r;
	else return a.id>b.id;
}

int ans[333333];
vector<circle> vec;
map<ii,vector<circle> > ma;

void init(int R)
{
	ma.clear();
	for(int i=0;i<vec.size();i++)
	{
		if(!ans[vec[i].id])
		{
			ma[mp(vec[i].x/R, vec[i].y/R)].pb(vec[i]);
		}
	}
}

bool intersect(circle x, circle y)
{
	ll d = (x.x-y.x)*1LL*(x.x-y.x) + (x.y-y.y)*1LL*(x.y-y.y);
	return (d<=(x.r+y.r)*1LL*(x.r+y.r));
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n; 
	for(int i=0;i<n;i++)
	{
		int x,y,r; cin>>x>>y>>r;
		vec.pb(circle(x,y,r,i+1));
	}
	sort(vec.rbegin(),vec.rend());
	int curC = int(1e9); init(curC);
	for(int i=0;i<vec.size();i++)
	{
		if(ans[vec[i].id]) continue;
		while(vec[i].r*2<curC)
		{
			curC/=2; init(curC);
		}
		int x=vec[i].x/curC; int y=vec[i].y/curC;
		for(int dx=-2;dx<=2;dx++)
		{
			for(int dy=-2;dy<=2;dy++)
			{
				int x2=x+dx; int y2=y+dy;
				if(ma.find(mp(x2,y2))==ma.end()) continue;
				for(auto it = ma[mp(x2,y2)].begin(); it != ma[mp(x2,y2)].end();)
				{
					if(intersect(*it, vec[i]))
					{
						ans[it->id] = vec[i].id;
						it = ma[mp(x2,y2)].erase(it);
					}
					else
					{
						it++;
					}
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		cout<<ans[i];
		if(i+1<=n) cout<<' ';
	}
	cout<<'\n';
}

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

circle_selection.cpp: In function 'void init(int)':
circle_selection.cpp:38:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<vec.size();i++)
              ~^~~~~~~~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<vec.size();i++)
              ~^~~~~~~~~~~

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