답안 #77739 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
77739	2018-09-30T06:48:07 Z	autumn_eel	원 고르기 (APIO18_circle_selection)	C++14	87 / 100	3000 ms	89832 KB

circle_selection

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define INF 1e10
#define EPS (1e-10)
using namespace std;

int ans[400000];
struct Circle{
	double x,y,r;
	int id;
	double bbox[2][2];
	Circle(){}
	Circle(double x,double y,double 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{
	double bbox[2][2];
	node*l,*r;
	vector<Circle*>circle;
};
double area(double bbox[2][2]){
	return (bbox[1][0]-bbox[0][0])*(bbox[1][1]-bbox[0][1]);
}
void init(double bbox[2][2]){
	bbox[0][0]=bbox[0][1]=INF;
	bbox[1][0]=bbox[1][1]=-INF;
}
void mergeAABB(double bbox[2][2],double bbox2[2][2],double 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,double 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);
	double Min=t_tri*circle.size();
	int axis=-1,id=-1;
	double s=area(n->bbox);
	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;
		});
		double box[2][2];init(box);
		vector<double>s1(circle.size());
		rep(j,circle.size()){
			mergeAABB(box,circle[j]->bbox,box);
			s1[j]=area(box);
		}
		init(box);
		vector<double>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++){
			double cost=2*t_aabb+(s1[j]/s)*(j+1)*t_tri+(s2[j+1]/s)*(circle.size()-j-1)*t_tri;
			if(Min>cost){
				Min=cost;
				axis=i;id=j;
			}
		}
	}
	if(axis==-1){
		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(double x,double y,double minx,double miny,double maxx,double maxy){
	return minx<=x&&x<=maxx&&miny<=y&&y<=maxy;
}
bool intersect(Circle*c1,Circle*c2){
	return pow(c1->x-c2->x,2)+pow(c1->y-c2->y,2)<=pow(c1->r+c2->r,2);
}
inline bool intersect(double bbox1[2][2],double 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;
	}
}

Circle c[400000];
int main(){
	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/128.,y/128.,r/128.,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("%d",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:64:3: note: in expansion of macro 'rep'
   rep(j,circle.size()){
   ^~~
circle_selection.cpp:74: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:131:3: note: in expansion of macro 'rep'
   rep(i,circle.size()){
   ^~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:148: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:151: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.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	30072 KB	Output is correct
2	Correct	28 ms	30256 KB	Output is correct
3	Correct	28 ms	30256 KB	Output is correct
4	Correct	27 ms	30300 KB	Output is correct
5	Correct	27 ms	30300 KB	Output is correct
6	Correct	32 ms	30372 KB	Output is correct
7	Correct	28 ms	30412 KB	Output is correct
8	Correct	27 ms	30412 KB	Output is correct
9	Correct	28 ms	30412 KB	Output is correct
10	Correct	28 ms	30412 KB	Output is correct
11	Correct	27 ms	30412 KB	Output is correct
12	Correct	28 ms	30412 KB	Output is correct
13	Correct	28 ms	30412 KB	Output is correct
14	Correct	27 ms	30412 KB	Output is correct
15	Correct	28 ms	30412 KB	Output is correct
16	Correct	30 ms	30460 KB	Output is correct
17	Correct	29 ms	30460 KB	Output is correct
18	Correct	29 ms	30460 KB	Output is correct
19	Correct	42 ms	30832 KB	Output is correct
20	Correct	42 ms	30844 KB	Output is correct
21	Correct	46 ms	30860 KB	Output is correct
22	Correct	47 ms	30860 KB	Output is correct
23	Correct	47 ms	30880 KB	Output is correct
24	Correct	48 ms	30908 KB	Output is correct
25	Correct	47 ms	30908 KB	Output is correct
26	Correct	49 ms	30908 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1748 ms	61652 KB	Output is correct
2	Correct	1684 ms	61652 KB	Output is correct
3	Correct	1850 ms	61652 KB	Output is correct
4	Correct	1822 ms	61652 KB	Output is correct
5	Correct	1670 ms	61652 KB	Output is correct
6	Correct	1836 ms	62056 KB	Output is correct
7	Correct	1746 ms	62056 KB	Output is correct
8	Correct	1609 ms	62056 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	62056 KB	Output is correct
2	Correct	710 ms	62056 KB	Output is correct
3	Correct	2770 ms	63952 KB	Output is correct
4	Correct	2741 ms	64080 KB	Output is correct
5	Correct	2571 ms	64080 KB	Output is correct
6	Correct	1079 ms	64080 KB	Output is correct
7	Correct	481 ms	64080 KB	Output is correct
8	Correct	129 ms	64080 KB	Output is correct
9	Correct	2839 ms	64080 KB	Output is correct
10	Correct	2620 ms	64080 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2695 ms	64116 KB	Output is correct
2	Correct	2747 ms	64116 KB	Output is correct
3	Correct	2279 ms	64116 KB	Output is correct
4	Correct	2788 ms	64116 KB	Output is correct
5	Correct	2666 ms	64116 KB	Output is correct
6	Correct	2329 ms	64116 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	30072 KB	Output is correct
2	Correct	28 ms	30256 KB	Output is correct
3	Correct	28 ms	30256 KB	Output is correct
4	Correct	27 ms	30300 KB	Output is correct
5	Correct	27 ms	30300 KB	Output is correct
6	Correct	32 ms	30372 KB	Output is correct
7	Correct	28 ms	30412 KB	Output is correct
8	Correct	27 ms	30412 KB	Output is correct
9	Correct	28 ms	30412 KB	Output is correct
10	Correct	28 ms	30412 KB	Output is correct
11	Correct	27 ms	30412 KB	Output is correct
12	Correct	28 ms	30412 KB	Output is correct
13	Correct	28 ms	30412 KB	Output is correct
14	Correct	27 ms	30412 KB	Output is correct
15	Correct	28 ms	30412 KB	Output is correct
16	Correct	30 ms	30460 KB	Output is correct
17	Correct	29 ms	30460 KB	Output is correct
18	Correct	29 ms	30460 KB	Output is correct
19	Correct	42 ms	30832 KB	Output is correct
20	Correct	42 ms	30844 KB	Output is correct
21	Correct	46 ms	30860 KB	Output is correct
22	Correct	47 ms	30860 KB	Output is correct
23	Correct	47 ms	30880 KB	Output is correct
24	Correct	48 ms	30908 KB	Output is correct
25	Correct	47 ms	30908 KB	Output is correct
26	Correct	49 ms	30908 KB	Output is correct
27	Correct	61 ms	64116 KB	Output is correct
28	Correct	61 ms	64116 KB	Output is correct
29	Correct	78 ms	64116 KB	Output is correct
30	Correct	70 ms	64116 KB	Output is correct
31	Correct	70 ms	64116 KB	Output is correct
32	Correct	70 ms	64116 KB	Output is correct
33	Correct	500 ms	64116 KB	Output is correct
34	Correct	528 ms	64116 KB	Output is correct
35	Correct	506 ms	64116 KB	Output is correct
36	Correct	656 ms	64116 KB	Output is correct
37	Correct	681 ms	64116 KB	Output is correct
38	Correct	702 ms	64116 KB	Output is correct
39	Correct	842 ms	64116 KB	Output is correct
40	Correct	897 ms	64116 KB	Output is correct
41	Correct	743 ms	64116 KB	Output is correct
42	Correct	488 ms	64116 KB	Output is correct
43	Correct	446 ms	64116 KB	Output is correct
44	Correct	438 ms	64116 KB	Output is correct
45	Correct	463 ms	64116 KB	Output is correct
46	Correct	441 ms	64116 KB	Output is correct
47	Correct	454 ms	64116 KB	Output is correct
48	Correct	499 ms	64116 KB	Output is correct
49	Correct	457 ms	64116 KB	Output is correct
50	Correct	447 ms	64116 KB	Output is correct

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	30072 KB	Output is correct
2	Correct	28 ms	30256 KB	Output is correct
3	Correct	28 ms	30256 KB	Output is correct
4	Correct	27 ms	30300 KB	Output is correct
5	Correct	27 ms	30300 KB	Output is correct
6	Correct	32 ms	30372 KB	Output is correct
7	Correct	28 ms	30412 KB	Output is correct
8	Correct	27 ms	30412 KB	Output is correct
9	Correct	28 ms	30412 KB	Output is correct
10	Correct	28 ms	30412 KB	Output is correct
11	Correct	27 ms	30412 KB	Output is correct
12	Correct	28 ms	30412 KB	Output is correct
13	Correct	28 ms	30412 KB	Output is correct
14	Correct	27 ms	30412 KB	Output is correct
15	Correct	28 ms	30412 KB	Output is correct
16	Correct	30 ms	30460 KB	Output is correct
17	Correct	29 ms	30460 KB	Output is correct
18	Correct	29 ms	30460 KB	Output is correct
19	Correct	42 ms	30832 KB	Output is correct
20	Correct	42 ms	30844 KB	Output is correct
21	Correct	46 ms	30860 KB	Output is correct
22	Correct	47 ms	30860 KB	Output is correct
23	Correct	47 ms	30880 KB	Output is correct
24	Correct	48 ms	30908 KB	Output is correct
25	Correct	47 ms	30908 KB	Output is correct
26	Correct	49 ms	30908 KB	Output is correct
27	Correct	1748 ms	61652 KB	Output is correct
28	Correct	1684 ms	61652 KB	Output is correct
29	Correct	1850 ms	61652 KB	Output is correct
30	Correct	1822 ms	61652 KB	Output is correct
31	Correct	1670 ms	61652 KB	Output is correct
32	Correct	1836 ms	62056 KB	Output is correct
33	Correct	1746 ms	62056 KB	Output is correct
34	Correct	1609 ms	62056 KB	Output is correct
35	Correct	28 ms	62056 KB	Output is correct
36	Correct	710 ms	62056 KB	Output is correct
37	Correct	2770 ms	63952 KB	Output is correct
38	Correct	2741 ms	64080 KB	Output is correct
39	Correct	2571 ms	64080 KB	Output is correct
40	Correct	1079 ms	64080 KB	Output is correct
41	Correct	481 ms	64080 KB	Output is correct
42	Correct	129 ms	64080 KB	Output is correct
43	Correct	2839 ms	64080 KB	Output is correct
44	Correct	2620 ms	64080 KB	Output is correct
45	Correct	2695 ms	64116 KB	Output is correct
46	Correct	2747 ms	64116 KB	Output is correct
47	Correct	2279 ms	64116 KB	Output is correct
48	Correct	2788 ms	64116 KB	Output is correct
49	Correct	2666 ms	64116 KB	Output is correct
50	Correct	2329 ms	64116 KB	Output is correct
51	Correct	61 ms	64116 KB	Output is correct
52	Correct	61 ms	64116 KB	Output is correct
53	Correct	78 ms	64116 KB	Output is correct
54	Correct	70 ms	64116 KB	Output is correct
55	Correct	70 ms	64116 KB	Output is correct
56	Correct	70 ms	64116 KB	Output is correct
57	Correct	500 ms	64116 KB	Output is correct
58	Correct	528 ms	64116 KB	Output is correct
59	Correct	506 ms	64116 KB	Output is correct
60	Correct	656 ms	64116 KB	Output is correct
61	Correct	681 ms	64116 KB	Output is correct
62	Correct	702 ms	64116 KB	Output is correct
63	Correct	842 ms	64116 KB	Output is correct
64	Correct	897 ms	64116 KB	Output is correct
65	Correct	743 ms	64116 KB	Output is correct
66	Correct	488 ms	64116 KB	Output is correct
67	Correct	446 ms	64116 KB	Output is correct
68	Correct	438 ms	64116 KB	Output is correct
69	Correct	463 ms	64116 KB	Output is correct
70	Correct	441 ms	64116 KB	Output is correct
71	Correct	454 ms	64116 KB	Output is correct
72	Correct	499 ms	64116 KB	Output is correct
73	Correct	457 ms	64116 KB	Output is correct
74	Correct	447 ms	64116 KB	Output is correct
75	Correct	2181 ms	70432 KB	Output is correct
76	Correct	2185 ms	76552 KB	Output is correct
77	Correct	2177 ms	76588 KB	Output is correct
78	Correct	2180 ms	76588 KB	Output is correct
79	Correct	2234 ms	76588 KB	Output is correct
80	Correct	2171 ms	76588 KB	Output is correct
81	Correct	2746 ms	79228 KB	Output is correct
82	Correct	2848 ms	79408 KB	Output is correct
83	Correct	2735 ms	79408 KB	Output is correct
84	Correct	2974 ms	79408 KB	Output is correct
85	Correct	2747 ms	79408 KB	Output is correct
86	Correct	2725 ms	79408 KB	Output is correct
87	Correct	2703 ms	79408 KB	Output is correct
88	Execution timed out	3048 ms	89832 KB	Time limit exceeded
89	Halted	0 ms	0 KB	-

답안 #77739

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 12.0 / 12.0

Subtask #3 15.0 / 15.0

Subtask #4 23.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
15.0 / 15.0

Subtask #4
23.0 / 23.0

Subtask #5
30.0 / 30.0

Subtask #6
0 / 13.0