답안 #77720 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
77720	2018-09-30T04:18:58 Z	autumn_eel	원 고르기 (APIO18_circle_selection)	C++14	49 / 100	3000 ms	71532 KB

circle_selection

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
#define int long long
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;
};
ll area(int bbox[2][2]){
	return (bbox[1][0]-bbox[0][0])*(ll)(bbox[1][1]-bbox[0][1]);
}
void init(int bbox[2][2]){
	bbox[0][0]=bbox[0][1]=INT_MAX;
	bbox[1][0]=bbox[1][1]=-INT_MAX;
}
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;

#define t_tri 1
#define t_aabb 1

void setleaf(vector<Circle*>circle,node*n){
	n->l=n->r=NULL;
	n->circle=circle;
}
void build(vector<Circle*>&circle,node*n){
	createAABB(circle,n->bbox);
	ll Min=LLONG_MAX;
	int axis=-1,id=-1;
	rep(i,2){
		sort(circle.begin(),circle.end(),[&](auto a,auto b){
			if(i==0)return a->x<b->x;
			return a->y<b->y;
		});
		int box[2][2];init(box);
		vector<ll>s1(circle.size());
		rep(j,circle.size()){
			mergeAABB(box,circle[j]->bbox,box);
			s1[j]=area(box);
		}
		init(box);
		vector<ll>s2(circle.size());
		for(int j=circle.size()-1;j>=0;j--){
			mergeAABB(box,circle[j]->bbox,box);
			s2[j]=area(box);
		}
		for(int j=0;j+1<circle.size();j++){
			ll cost=(s1[j])*(ll)(j+1)+(s2[j+1])*(ll)(circle.size()-j-1);
			if(Min>cost){
				Min=cost;
				axis=i;id=j;
			}
		}
	}
	if(axis==-1||t_tri*circle.size()<2*t_aabb+Min*t_tri/(double)area(n->bbox)){
		setleaf(circle,n);
	}
	else{
		sort(circle.begin(),circle.end(),[&](auto a,auto b){
			if(axis==0)return a->x<b->x;
			return a->y<b->y;
		});
		n->l=&bvh[pointer++];
		n->r=&bvh[pointer++];
		vector<Circle*>left(circle.begin(),circle.begin()+id+1);
		vector<Circle*>right(circle.begin()+id+1,circle.end());
		build(left,n->l);
		build(right,n->r);
	}
}
void dfs_bvh(node*n,int depth){
	if(depth==3){
		cout<<"(minx,miny),(maxx,maxy) = "<<"("<<n->bbox[0][0]<<","<<n->bbox[0][1]<<")"<<","<<"("<<n->bbox[1][0]<<","<<n->bbox[1][1]<<")"<<endl;
	}
	if(n->l)dfs_bvh(n->l,depth+1);
	if(n->r)dfs_bvh(n->r,depth+1);
}
bool intersect(int x,int y,int minx,int miny,int maxx,int maxy){
	return minx<=x&&x<=maxx&&miny<=y&&y<=maxy;
}
bool intersect(Circle*c1,Circle*c2){
	return (c1->x-c2->x)*(ll)(c1->x-c2->x)+(c1->y-c2->y)*(ll)(c1->y-c2->y)
			<=(c1->r+c2->r)*(ll)(c1->r+c2->r);
}
bool intersect(Circle*c,int bbox[2][2]){
	if(intersect(c->x,c->y,bbox[0][0]-c->r,bbox[0][1],bbox[1][0]+c->r,bbox[1][1]))return true;
	if(intersect(c->x,c->y,bbox[0][0],bbox[0][1]-c->r,bbox[1][0],bbox[1][1]+c->r))return true;
	rep(i,2)rep(j,2){
		if((bbox[i][0]-c->x)*(ll)(bbox[i][0]-c->x)+(bbox[j][1]-c->y)*(ll)(bbox[j][1]-c->y)
			<=(c->r)*(ll)(c->r))return true;
	}
	return false;
}
node*intersect(node*n,Circle*c){
	if(!intersect(c,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;
	}
}

Circle c[400000];

signed main(){
	int n;scanf("%lld",&n);
	vector<Circle*>circle;
	rep(i,n){
		int x,y,r;scanf("%lld%lld%lld",&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);
	//~ dfs_bvh(root,0);
	memset(ans,-1,sizeof(ans));
	rep(i,n){
		if(ans[c[i].id]!=-1)continue;
		root=intersect(root,&c[i]);
		if(root==NULL)break;
	}
	rep(i,n){
		if(i)printf(" ");
		printf("%lld",ans[i]+1);
	}
	puts("");
}

Compilation message

circle_selection.cpp: In function 'void build(std::vector<Circle*>&, node*)':
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:63:3: note: in expansion of macro 'rep'
   rep(j,circle.size()){
   ^~~
circle_selection.cpp:73:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j+1<circle.size();j++){
               ~~~^~~~~~~~~~~~~~
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:136:3: note: in expansion of macro 'rep'
   rep(i,circle.size()){
   ^~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:154:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n;scanf("%lld",&n);
        ~~~~~^~~~~~~~~~~
circle_selection.cpp:157:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x,y,r;scanf("%lld%lld%lld",&x,&y,&r);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	31608 KB	Output is correct
2	Correct	30 ms	31744 KB	Output is correct
3	Correct	29 ms	31924 KB	Output is correct
4	Correct	27 ms	31924 KB	Output is correct
5	Correct	28 ms	31924 KB	Output is correct
6	Correct	31 ms	31932 KB	Output is correct
7	Correct	29 ms	31932 KB	Output is correct
8	Correct	30 ms	31932 KB	Output is correct
9	Correct	30 ms	31932 KB	Output is correct
10	Correct	33 ms	31932 KB	Output is correct
11	Correct	29 ms	32076 KB	Output is correct
12	Correct	28 ms	32076 KB	Output is correct
13	Correct	28 ms	32076 KB	Output is correct
14	Correct	34 ms	32076 KB	Output is correct
15	Correct	32 ms	32076 KB	Output is correct
16	Correct	34 ms	32076 KB	Output is correct
17	Correct	31 ms	32132 KB	Output is correct
18	Correct	39 ms	32132 KB	Output is correct
19	Correct	47 ms	32804 KB	Output is correct
20	Correct	50 ms	32916 KB	Output is correct
21	Correct	50 ms	33084 KB	Output is correct
22	Correct	49 ms	33240 KB	Output is correct
23	Correct	48 ms	33284 KB	Output is correct
24	Correct	49 ms	33504 KB	Output is correct
25	Correct	50 ms	33628 KB	Output is correct
26	Correct	48 ms	33720 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2155 ms	71532 KB	Output is correct
2	Correct	1722 ms	71532 KB	Output is correct
3	Correct	1973 ms	71532 KB	Output is correct
4	Correct	1911 ms	71532 KB	Output is correct
5	Correct	1458 ms	71532 KB	Output is correct
6	Correct	1615 ms	71532 KB	Output is correct
7	Correct	1486 ms	71532 KB	Output is correct
8	Correct	1558 ms	71532 KB	Output is correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	71532 KB	Output is correct
2	Correct	768 ms	71532 KB	Output is correct
3	Execution timed out	3055 ms	71532 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	3009 ms	71532 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	31608 KB	Output is correct
2	Correct	30 ms	31744 KB	Output is correct
3	Correct	29 ms	31924 KB	Output is correct
4	Correct	27 ms	31924 KB	Output is correct
5	Correct	28 ms	31924 KB	Output is correct
6	Correct	31 ms	31932 KB	Output is correct
7	Correct	29 ms	31932 KB	Output is correct
8	Correct	30 ms	31932 KB	Output is correct
9	Correct	30 ms	31932 KB	Output is correct
10	Correct	33 ms	31932 KB	Output is correct
11	Correct	29 ms	32076 KB	Output is correct
12	Correct	28 ms	32076 KB	Output is correct
13	Correct	28 ms	32076 KB	Output is correct
14	Correct	34 ms	32076 KB	Output is correct
15	Correct	32 ms	32076 KB	Output is correct
16	Correct	34 ms	32076 KB	Output is correct
17	Correct	31 ms	32132 KB	Output is correct
18	Correct	39 ms	32132 KB	Output is correct
19	Correct	47 ms	32804 KB	Output is correct
20	Correct	50 ms	32916 KB	Output is correct
21	Correct	50 ms	33084 KB	Output is correct
22	Correct	49 ms	33240 KB	Output is correct
23	Correct	48 ms	33284 KB	Output is correct
24	Correct	49 ms	33504 KB	Output is correct
25	Correct	50 ms	33628 KB	Output is correct
26	Correct	48 ms	33720 KB	Output is correct
27	Correct	76 ms	71532 KB	Output is correct
28	Correct	66 ms	71532 KB	Output is correct
29	Correct	66 ms	71532 KB	Output is correct
30	Correct	75 ms	71532 KB	Output is correct
31	Correct	77 ms	71532 KB	Output is correct
32	Correct	74 ms	71532 KB	Output is correct
33	Correct	693 ms	71532 KB	Output is correct
34	Correct	681 ms	71532 KB	Output is correct
35	Correct	619 ms	71532 KB	Output is correct
36	Correct	682 ms	71532 KB	Output is correct
37	Correct	723 ms	71532 KB	Output is correct
38	Correct	738 ms	71532 KB	Output is correct
39	Correct	629 ms	71532 KB	Output is correct
40	Correct	552 ms	71532 KB	Output is correct
41	Correct	559 ms	71532 KB	Output is correct
42	Correct	462 ms	71532 KB	Output is correct
43	Correct	527 ms	71532 KB	Output is correct
44	Correct	544 ms	71532 KB	Output is correct
45	Correct	466 ms	71532 KB	Output is correct
46	Correct	465 ms	71532 KB	Output is correct
47	Correct	471 ms	71532 KB	Output is correct
48	Correct	514 ms	71532 KB	Output is correct
49	Correct	469 ms	71532 KB	Output is correct
50	Correct	498 ms	71532 KB	Output is correct

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	31608 KB	Output is correct
2	Correct	30 ms	31744 KB	Output is correct
3	Correct	29 ms	31924 KB	Output is correct
4	Correct	27 ms	31924 KB	Output is correct
5	Correct	28 ms	31924 KB	Output is correct
6	Correct	31 ms	31932 KB	Output is correct
7	Correct	29 ms	31932 KB	Output is correct
8	Correct	30 ms	31932 KB	Output is correct
9	Correct	30 ms	31932 KB	Output is correct
10	Correct	33 ms	31932 KB	Output is correct
11	Correct	29 ms	32076 KB	Output is correct
12	Correct	28 ms	32076 KB	Output is correct
13	Correct	28 ms	32076 KB	Output is correct
14	Correct	34 ms	32076 KB	Output is correct
15	Correct	32 ms	32076 KB	Output is correct
16	Correct	34 ms	32076 KB	Output is correct
17	Correct	31 ms	32132 KB	Output is correct
18	Correct	39 ms	32132 KB	Output is correct
19	Correct	47 ms	32804 KB	Output is correct
20	Correct	50 ms	32916 KB	Output is correct
21	Correct	50 ms	33084 KB	Output is correct
22	Correct	49 ms	33240 KB	Output is correct
23	Correct	48 ms	33284 KB	Output is correct
24	Correct	49 ms	33504 KB	Output is correct
25	Correct	50 ms	33628 KB	Output is correct
26	Correct	48 ms	33720 KB	Output is correct
27	Correct	2155 ms	71532 KB	Output is correct
28	Correct	1722 ms	71532 KB	Output is correct
29	Correct	1973 ms	71532 KB	Output is correct
30	Correct	1911 ms	71532 KB	Output is correct
31	Correct	1458 ms	71532 KB	Output is correct
32	Correct	1615 ms	71532 KB	Output is correct
33	Correct	1486 ms	71532 KB	Output is correct
34	Correct	1558 ms	71532 KB	Output is correct
35	Correct	29 ms	71532 KB	Output is correct
36	Correct	768 ms	71532 KB	Output is correct
37	Execution timed out	3055 ms	71532 KB	Time limit exceeded
38	Halted	0 ms	0 KB	-

답안 #77720

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 12.0 / 12.0

Subtask #3 0 / 15.0

Subtask #4 0 / 23.0

Subtask #5 30.0 / 30.0

Subtask #6 0 / 13.0

Subtask #1
7.0 / 7.0

Subtask #2
12.0 / 12.0

Subtask #3
0 / 15.0

Subtask #4
0 / 23.0

Subtask #5
30.0 / 30.0

Subtask #6
0 / 13.0