제출 #77875

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
77875		autumn_eel	원 고르기 (APIO18_circle_selection)	C++14	100 / 100	904 ms	48108 KiB

circle_selection

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define INF INT_MAX
using namespace std;
typedef long long ll;
 
int ans[400000];
struct Circle{
	int x,y,r;
	int id;
	int bbox[2][2];
	Circle(){}
	Circle(int x,int y,int r,int id):x(x),y(y),r(r),id(id){
		bbox[0][0]=x-r;bbox[0][1]=y-r;
		bbox[1][0]=x+r;bbox[1][1]=y+r;
	}
};
struct node{
	int bbox[2][2];
	node*l,*r;
	vector<Circle*>circle;
};
void init(int bbox[2][2]){
	bbox[0][0]=bbox[0][1]=INF;
	bbox[1][0]=bbox[1][1]=-INF;
}
void mergeAABB(int bbox[2][2],int bbox2[2][2],int result[2][2]){
	rep(i,2){
		result[0][i]=min(bbox[0][i],bbox2[0][i]);
		result[1][i]=max(bbox[1][i],bbox2[1][i]);
	}
}
void createAABB(vector<Circle*>&circle,int result[2][2]){
	init(result);
	for(auto&c:circle){
		mergeAABB(result,c->bbox,result);
	}
}
node bvh[400000];
int pointer=0;

inline void setleaf(vector<Circle*>circle,node*n){
	n->l=n->r=NULL;
	n->circle=circle;
}
struct st{
	int cost;
	int id;
	bool operator<(const st&r)const{
		return cost<r.cost;
	}
};
void build(vector<Circle*>&circle,node*n,int depth){
	createAABB(circle,n->bbox);
	if(circle.size()<=2){
		setleaf(circle,n);
		return;
	}
	int axis=-1;
	int minx=INF,maxx=-INF,miny=INF,maxy=-INF;
	rep(i,circle.size()){
		minx=min(minx,circle[i]->bbox[0][0]);
		maxx=max(maxx,circle[i]->bbox[1][0]);
		miny=min(miny,circle[i]->bbox[0][1]);
		maxy=max(maxy,circle[i]->bbox[1][1]);
	}
	if(maxx-minx>maxy-miny)axis=0;
	else axis=1;
	
	n->l=&bvh[pointer++];
	n->r=&bvh[pointer++];
	int id=circle.size()/2;
	nth_element(circle.begin(),circle.begin()+id,circle.end(),[&](auto a,auto b){
		if(axis==0)return a->x<b->x;
		return a->y<b->y;
	});
	vector<Circle*>left(circle.begin(),circle.begin()+id);
	vector<Circle*>right(circle.begin()+id,circle.end());
	build(left,n->l,depth+1);
	build(right,n->r,depth+1);
}
inline ll sq(int x){
	return x*(ll)x;
}
inline bool intersect(Circle*c1,Circle*c2){
	return sq(c1->x-c2->x)+sq(c1->y-c2->y)<=sq(c1->r+c2->r);
}
inline bool intersect(int bbox1[2][2],int bbox2[2][2]){
	if(bbox1[1][0]<bbox2[0][0]||bbox2[1][0]<bbox1[0][0]||bbox1[1][1]<bbox2[0][1]||bbox2[1][1]<bbox1[0][1])return false;
	return true;
}
node*intersect(node*n,Circle*c){
	if(!intersect(c->bbox,n->bbox))return n;
	if(n->l){
		auto l=intersect(n->l,c);
		auto r=intersect(n->r,c);
		if(l==NULL&&r==NULL)return NULL;
		if(l==NULL)return r;
		if(r==NULL)return l;
		n->l=l;n->r=r;
		init(n->bbox);
		mergeAABB(l->bbox,r->bbox,n->bbox);
		return n;
	}
	else{
		auto&circle=n->circle;
		vector<Circle*>res;
		rep(i,circle.size()){
			if(intersect(circle[i],c)){
				ans[circle[i]->id]=c->id;
			}
			else{
				res.push_back(circle[i]);
			}
		}
		if(res.empty())return NULL;
		circle=res;
		createAABB(circle,n->bbox);
		return n;
	}
}
 
//~ #define DEBUG
Circle c[400000];
 
int main(){
#ifdef DEBUG
	auto start=chrono::system_clock::now();
#endif
	int n;scanf("%d",&n);
	vector<Circle*>circle;
	rep(i,n){
		int x,y,r;scanf("%d%d%d",&x,&y,&r);
		c[i]=Circle(x,y,r,i);
	}
	sort(c,c+n,[](auto a,auto b){
		if(a.r==b.r)return a.id<b.id;
		return a.r>b.r;
	});
	rep(i,n){
		circle.push_back(&c[i]);
	}
	node*root=&bvh[pointer++];
	build(circle,root,0);
#ifdef DEBUG
	auto end=chrono::system_clock::now();
	double tim=chrono::duration_cast<chrono::milliseconds>(end-start).count();
	printf("build time = %.3lf sec\n",tim/1000);
#endif
	memset(ans,-1,sizeof(ans));
	rep(i,n){
		if(ans[c[i].id]!=-1)continue;
		root=intersect(root,&c[i]);
		if(root==NULL)break;
	}
#ifndef DEBUG
	rep(i,n){
		if(i)printf(" ");
		printf("%d",ans[i]+1);
	}
	puts("");
#endif
#ifdef DEBUG
	auto end2=chrono::system_clock::now();
	double tim2=chrono::duration_cast<chrono::milliseconds>(end2-end).count();
	printf("intersection time = %.3lf sec\n",tim2/1000);
	double tim3=chrono::duration_cast<chrono::milliseconds>(end2-start).count();
	printf("total time = %.3lf sec\n",tim3/1000);
#endif
}

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

circle_selection.cpp: In function 'void build(std::vector<Circle*>&, node*, int)':
circle_selection.cpp:2:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n)for(int i=0;i<(n);i++)
                              ^
circle_selection.cpp:61:2: note: in expansion of macro 'rep'
  rep(i,circle.size()){
  ^~~
circle_selection.cpp: In function 'node* intersect(node*, Circle*)':
circle_selection.cpp:2:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n)for(int i=0;i<(n);i++)
                              ^
circle_selection.cpp:108:3: note: in expansion of macro 'rep'
   rep(i,circle.size()){
   ^~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:130:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n;scanf("%d",&n);
        ~~~~~^~~~~~~~~
circle_selection.cpp:133:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x,y,r;scanf("%d%d%d",&x,&y,&r);
             ~~~~~^~~~~~~~~~~~~~~~~~~

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