oj.uz

Submission #77722

# Submission time Handle Problem Language Result Execution time Memory
77722 2018-09-30T04:54:32 Z autumn_eel Circle selection (APIO18_circle_selection) C++14
72 / 100
 3000 ms 53148 KB 
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
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;
};
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,ll minx,ll miny,ll maxx,ll 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]-(ll)c->r,bbox[0][1],bbox[1][0]+(ll)c->r,bbox[1][1]))return true;
	if(intersect(c->x,c->y,bbox[0][0],bbox[0][1]-(ll)c->r,bbox[1][0],bbox[1][1]+(ll)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("%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);
	//~ 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:62:3: note: in expansion of macro 'rep'
   rep(j,circle.size()){
   ^~~
circle_selection.cpp:72: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:135:3: note: in expansion of macro 'rep'
   rep(i,circle.size()){
   ^~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:153: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:156: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

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23800 KB Output is correct
2 Correct 21 ms 23936 KB Output is correct
3 Correct 24 ms 24016 KB Output is correct
4 Correct 22 ms 24016 KB Output is correct
5 Correct 22 ms 24112 KB Output is correct
6 Correct 22 ms 24112 KB Output is correct
7 Correct 21 ms 24112 KB Output is correct
8 Correct 22 ms 24112 KB Output is correct
9 Correct 22 ms 24112 KB Output is correct
10 Correct 21 ms 24112 KB Output is correct
11 Correct 22 ms 24112 KB Output is correct
12 Correct 21 ms 24112 KB Output is correct
13 Correct 22 ms 24112 KB Output is correct
14 Correct 21 ms 24112 KB Output is correct
15 Correct 22 ms 24144 KB Output is correct
16 Correct 43 ms 24220 KB Output is correct
17 Correct 24 ms 24252 KB Output is correct
18 Correct 25 ms 24284 KB Output is correct
19 Correct 41 ms 24828 KB Output is correct
20 Correct 42 ms 24832 KB Output is correct
21 Correct 40 ms 24832 KB Output is correct
22 Correct 44 ms 24832 KB Output is correct
23 Correct 40 ms 24832 KB Output is correct
24 Correct 42 ms 24832 KB Output is correct
25 Correct 46 ms 24840 KB Output is correct
26 Correct 41 ms 24840 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1789 ms 52928 KB Output is correct
2 Correct 1624 ms 52928 KB Output is correct
3 Correct 1718 ms 52928 KB Output is correct
4 Correct 1773 ms 52928 KB Output is correct
5 Correct 1314 ms 52928 KB Output is correct
6 Correct 1514 ms 52928 KB Output is correct
7 Correct 1378 ms 52928 KB Output is correct
8 Correct 1342 ms 52928 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 52928 KB Output is correct
2 Correct 708 ms 52928 KB Output is correct
3 Execution timed out 3030 ms 53148 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2770 ms 53148 KB Output is correct
2 Correct 2730 ms 53148 KB Output is correct
3 Correct 2340 ms 53148 KB Output is correct
4 Correct 2969 ms 53148 KB Output is correct
5 Correct 2727 ms 53148 KB Output is correct
6 Correct 2331 ms 53148 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23800 KB Output is correct
2 Correct 21 ms 23936 KB Output is correct
3 Correct 24 ms 24016 KB Output is correct
4 Correct 22 ms 24016 KB Output is correct
5 Correct 22 ms 24112 KB Output is correct
6 Correct 22 ms 24112 KB Output is correct
7 Correct 21 ms 24112 KB Output is correct
8 Correct 22 ms 24112 KB Output is correct
9 Correct 22 ms 24112 KB Output is correct
10 Correct 21 ms 24112 KB Output is correct
11 Correct 22 ms 24112 KB Output is correct
12 Correct 21 ms 24112 KB Output is correct
13 Correct 22 ms 24112 KB Output is correct
14 Correct 21 ms 24112 KB Output is correct
15 Correct 22 ms 24144 KB Output is correct
16 Correct 43 ms 24220 KB Output is correct
17 Correct 24 ms 24252 KB Output is correct
18 Correct 25 ms 24284 KB Output is correct
19 Correct 41 ms 24828 KB Output is correct
20 Correct 42 ms 24832 KB Output is correct
21 Correct 40 ms 24832 KB Output is correct
22 Correct 44 ms 24832 KB Output is correct
23 Correct 40 ms 24832 KB Output is correct
24 Correct 42 ms 24832 KB Output is correct
25 Correct 46 ms 24840 KB Output is correct
26 Correct 41 ms 24840 KB Output is correct
27 Correct 61 ms 53148 KB Output is correct
28 Correct 60 ms 53148 KB Output is correct
29 Correct 61 ms 53148 KB Output is correct
30 Correct 67 ms 53148 KB Output is correct
31 Correct 73 ms 53148 KB Output is correct
32 Correct 75 ms 53148 KB Output is correct
33 Correct 687 ms 53148 KB Output is correct
34 Correct 685 ms 53148 KB Output is correct
35 Correct 638 ms 53148 KB Output is correct
36 Correct 744 ms 53148 KB Output is correct
37 Correct 735 ms 53148 KB Output is correct
38 Correct 741 ms 53148 KB Output is correct
39 Correct 617 ms 53148 KB Output is correct
40 Correct 553 ms 53148 KB Output is correct
41 Correct 594 ms 53148 KB Output is correct
42 Correct 468 ms 53148 KB Output is correct
43 Correct 493 ms 53148 KB Output is correct
44 Correct 588 ms 53148 KB Output is correct
45 Correct 508 ms 53148 KB Output is correct
46 Correct 480 ms 53148 KB Output is correct
47 Correct 487 ms 53148 KB Output is correct
48 Correct 503 ms 53148 KB Output is correct
49 Correct 481 ms 53148 KB Output is correct
50 Correct 514 ms 53148 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23800 KB Output is correct
2 Correct 21 ms 23936 KB Output is correct
3 Correct 24 ms 24016 KB Output is correct
4 Correct 22 ms 24016 KB Output is correct
5 Correct 22 ms 24112 KB Output is correct
6 Correct 22 ms 24112 KB Output is correct
7 Correct 21 ms 24112 KB Output is correct
8 Correct 22 ms 24112 KB Output is correct
9 Correct 22 ms 24112 KB Output is correct
10 Correct 21 ms 24112 KB Output is correct
11 Correct 22 ms 24112 KB Output is correct
12 Correct 21 ms 24112 KB Output is correct
13 Correct 22 ms 24112 KB Output is correct
14 Correct 21 ms 24112 KB Output is correct
15 Correct 22 ms 24144 KB Output is correct
16 Correct 43 ms 24220 KB Output is correct
17 Correct 24 ms 24252 KB Output is correct
18 Correct 25 ms 24284 KB Output is correct
19 Correct 41 ms 24828 KB Output is correct
20 Correct 42 ms 24832 KB Output is correct
21 Correct 40 ms 24832 KB Output is correct
22 Correct 44 ms 24832 KB Output is correct
23 Correct 40 ms 24832 KB Output is correct
24 Correct 42 ms 24832 KB Output is correct
25 Correct 46 ms 24840 KB Output is correct
26 Correct 41 ms 24840 KB Output is correct
27 Correct 1789 ms 52928 KB Output is correct
28 Correct 1624 ms 52928 KB Output is correct
29 Correct 1718 ms 52928 KB Output is correct
30 Correct 1773 ms 52928 KB Output is correct
31 Correct 1314 ms 52928 KB Output is correct
32 Correct 1514 ms 52928 KB Output is correct
33 Correct 1378 ms 52928 KB Output is correct
34 Correct 1342 ms 52928 KB Output is correct
35 Correct 27 ms 52928 KB Output is correct
36 Correct 708 ms 52928 KB Output is correct
37 Execution timed out 3030 ms 53148 KB Time limit exceeded
38 Halted 0 ms 0 KB -