답안 #50801 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
50801	2018-06-13T11:01:38 Z	hamzqq9	원 고르기 (APIO18_circle_selection)	C++14	45 / 100	1553 ms	75932 KB

circle_selection

#include<bits/stdc++.h>
#define lf double
#define ll long long
#define ull unsigned ll
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define iiii2 pair<int,iii>
#define lii pair<ll,ii>
#define lolo pair<ll,ll>
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)/2)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 1000000007
#define inf 1000000000
#define N 300005
#define LOG 20
#define magic 100
#define KOK 350
#define EPS 0.0025
#define pw(x) ((1ll)<<(x))
#define PI 3.1415926535
#define get(x,y) ((x<0)?(x+y):(x))
using namespace std;

struct Circle {

	int x,y,r,id;

};

int n,x,y,r,R=pw(30);
Circle T[N],C[N];
int take[N],p[N];
vector< vector<Circle> > V;

lf dist(ii x,ii y) {

	return sqrt(1ll*(x.st-y.st)*(x.st-y.st)+1ll*(x.nd-y.nd)*(x.nd-y.nd));

}

bool inter(Circle a,Circle b) {

	if(dist({a.x,a.y},{b.x,b.y})<=a.r+b.r) return true;

	return false;

}

void split() {

	vector< vector< Circle> > New;

	for(int i=0;i<sz(V);i++) {

		vector<Circle> down,up;

		int prvY=V[i][0].y-get(V[i][0].y%R,R);

		int midY=prvY+R/2-1;

		for(int j=0;j<sz(V[i]);j++) {

			Circle Now=V[i][j];

			if(take[Now.id]) continue ;

			if(Now.y<=midY) down.pb(Now);
			else up.pb(Now);

		}

		if(sz(down)) New.pb(down);
		if(sz(up)) New.pb(up);

	}

	V=New;

	R/=2;

}

void up(int ind) {

	while(T[ind].r<=R/2) {

		split();

	}

}

void solve(int now) {

	int pos=lower_bound(all(V),T[now],[&](const vector<Circle> &Cc,const Circle &Now){

		if(Cc[0].y<1ll*Now.y-2ll*R-get(Now.y%R,R)+1) return true;

		return false;

	})-V.begin();

	for(int i=pos;i<sz(V);i++) {

		if(V[i][0].y>1ll*T[now].y+3ll*R-get(T[now].y%R,R)-1) break ;

		int bas=lower_bound(all(V[i]),T[now],[&](const Circle &a,const Circle &b) {

			if(a.x<1ll*b.x-2ll*R-get(b.x%R,R)+1) return true;

			return false;
 
		})-V[i].begin();

		for(int j=bas;j<sz(V[i]);j++) {

			Circle Now=V[i][j];

			if(Now.x>1ll*T[now].x+3ll*R-get(T[now].y%R,R)-1) break ;

			if(!take[Now.id] && inter(Now,T[now])) {

				take[Now.id]=1;
				p[Now.id]=T[now].id;

			}

		}

	}

}

void build() {

	for(int i=1;i<=n;i++) {

		int nxtY=R-get(C[i].y%R,R)+C[i].y-1;

		vector<Circle> Push;

		while(i+1<=n && C[i+1].y<=nxtY) {
			
			Push.pb(C[i]);

			i++;

		}

		Push.pb(C[i]);

		sort(all(Push),[](Circle a,Circle b) {

			if(a.x<b.x) return true;

			return false;

		});

		V.pb(Push);

	}

}

int main() {

 	#if 0
	freopen("input.txt","r",stdin);
 	#endif

	scanf("%d",&n);

	for(int i=1;i<=n;i++) {

		scanf("%d %d %d",&x,&y,&r);

		C[i]={x,y,r,i};

		T[i]=C[i];

	}

	sort(C+1,C+1+n,[](Circle a,Circle b) {

		if(a.y<b.y) return true;

		if(a.y>b.y) return false;

		if(a.x<b.x) return true;

		return false;

	});

	sort(T+1,T+1+n,[](Circle a,Circle b) {

		if(a.r>b.r) return true;

		if(a.r<b.r) return false;

		if(a.id<b.id) return true;

		return false;

	});

	build();

	for(int i=1;i<=n;i++) {

		if(!take[T[i].id]) {

			up(i);

			solve(i);

		}
	}

	for(int i=1;i<=n;i++) printf("%d ",p[i]);

}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:190:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
circle_selection.cpp:194:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&x,&y,&r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	2 ms	432 KB	Output is correct
4	Correct	2 ms	448 KB	Output is correct
5	Correct	2 ms	484 KB	Output is correct
6	Correct	2 ms	484 KB	Output is correct
7	Correct	2 ms	484 KB	Output is correct
8	Correct	2 ms	536 KB	Output is correct
9	Correct	2 ms	588 KB	Output is correct
10	Correct	2 ms	588 KB	Output is correct
11	Correct	3 ms	684 KB	Output is correct
12	Correct	2 ms	684 KB	Output is correct
13	Correct	2 ms	684 KB	Output is correct
14	Correct	4 ms	684 KB	Output is correct
15	Correct	3 ms	684 KB	Output is correct
16	Correct	3 ms	684 KB	Output is correct
17	Correct	3 ms	684 KB	Output is correct
18	Correct	3 ms	684 KB	Output is correct
19	Correct	6 ms	972 KB	Output is correct
20	Correct	7 ms	972 KB	Output is correct
21	Correct	8 ms	1032 KB	Output is correct
22	Correct	15 ms	1536 KB	Output is correct
23	Correct	20 ms	1720 KB	Output is correct
24	Correct	17 ms	1720 KB	Output is correct
25	Correct	16 ms	1720 KB	Output is correct
26	Correct	16 ms	1720 KB	Output is correct

Subtask #2
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	275 ms	27736 KB	Output is correct
2	Correct	305 ms	27736 KB	Output is correct
3	Correct	291 ms	27736 KB	Output is correct
4	Correct	253 ms	27736 KB	Output is correct
5	Incorrect	493 ms	27840 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	27840 KB	Output is correct
2	Correct	211 ms	27840 KB	Output is correct
3	Correct	757 ms	28100 KB	Output is correct
4	Correct	842 ms	30264 KB	Output is correct
5	Correct	677 ms	30264 KB	Output is correct
6	Correct	289 ms	30264 KB	Output is correct
7	Correct	172 ms	30264 KB	Output is correct
8	Correct	38 ms	30264 KB	Output is correct
9	Correct	770 ms	30264 KB	Output is correct
10	Correct	606 ms	30264 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	809 ms	35900 KB	Output is correct
2	Correct	1553 ms	75932 KB	Output is correct
3	Correct	383 ms	75932 KB	Output is correct
4	Correct	1034 ms	75932 KB	Output is correct
5	Correct	916 ms	75932 KB	Output is correct
6	Correct	406 ms	75932 KB	Output is correct

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	2 ms	432 KB	Output is correct
4	Correct	2 ms	448 KB	Output is correct
5	Correct	2 ms	484 KB	Output is correct
6	Correct	2 ms	484 KB	Output is correct
7	Correct	2 ms	484 KB	Output is correct
8	Correct	2 ms	536 KB	Output is correct
9	Correct	2 ms	588 KB	Output is correct
10	Correct	2 ms	588 KB	Output is correct
11	Correct	3 ms	684 KB	Output is correct
12	Correct	2 ms	684 KB	Output is correct
13	Correct	2 ms	684 KB	Output is correct
14	Correct	4 ms	684 KB	Output is correct
15	Correct	3 ms	684 KB	Output is correct
16	Correct	3 ms	684 KB	Output is correct
17	Correct	3 ms	684 KB	Output is correct
18	Correct	3 ms	684 KB	Output is correct
19	Correct	6 ms	972 KB	Output is correct
20	Correct	7 ms	972 KB	Output is correct
21	Correct	8 ms	1032 KB	Output is correct
22	Correct	15 ms	1536 KB	Output is correct
23	Correct	20 ms	1720 KB	Output is correct
24	Correct	17 ms	1720 KB	Output is correct
25	Correct	16 ms	1720 KB	Output is correct
26	Correct	16 ms	1720 KB	Output is correct
27	Correct	12 ms	75932 KB	Output is correct
28	Correct	13 ms	75932 KB	Output is correct
29	Correct	12 ms	75932 KB	Output is correct
30	Correct	31 ms	75932 KB	Output is correct
31	Correct	23 ms	75932 KB	Output is correct
32	Correct	28 ms	75932 KB	Output is correct
33	Correct	104 ms	75932 KB	Output is correct
34	Correct	107 ms	75932 KB	Output is correct
35	Correct	107 ms	75932 KB	Output is correct
36	Correct	234 ms	75932 KB	Output is correct
37	Correct	246 ms	75932 KB	Output is correct
38	Correct	245 ms	75932 KB	Output is correct
39	Incorrect	277 ms	75932 KB	Output isn't correct
40	Halted	0 ms	0 KB	-

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	2 ms	432 KB	Output is correct
4	Correct	2 ms	448 KB	Output is correct
5	Correct	2 ms	484 KB	Output is correct
6	Correct	2 ms	484 KB	Output is correct
7	Correct	2 ms	484 KB	Output is correct
8	Correct	2 ms	536 KB	Output is correct
9	Correct	2 ms	588 KB	Output is correct
10	Correct	2 ms	588 KB	Output is correct
11	Correct	3 ms	684 KB	Output is correct
12	Correct	2 ms	684 KB	Output is correct
13	Correct	2 ms	684 KB	Output is correct
14	Correct	4 ms	684 KB	Output is correct
15	Correct	3 ms	684 KB	Output is correct
16	Correct	3 ms	684 KB	Output is correct
17	Correct	3 ms	684 KB	Output is correct
18	Correct	3 ms	684 KB	Output is correct
19	Correct	6 ms	972 KB	Output is correct
20	Correct	7 ms	972 KB	Output is correct
21	Correct	8 ms	1032 KB	Output is correct
22	Correct	15 ms	1536 KB	Output is correct
23	Correct	20 ms	1720 KB	Output is correct
24	Correct	17 ms	1720 KB	Output is correct
25	Correct	16 ms	1720 KB	Output is correct
26	Correct	16 ms	1720 KB	Output is correct
27	Correct	275 ms	27736 KB	Output is correct
28	Correct	305 ms	27736 KB	Output is correct
29	Correct	291 ms	27736 KB	Output is correct
30	Correct	253 ms	27736 KB	Output is correct
31	Incorrect	493 ms	27840 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

답안 #50801

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 0 / 12.0

Subtask #3 15.0 / 15.0

Subtask #4 23.0 / 23.0

Subtask #5 0 / 30.0

Subtask #6 0 / 13.0

Subtask #1
7.0 / 7.0

Subtask #2
0 / 12.0

Subtask #3
15.0 / 15.0

Subtask #4
23.0 / 23.0

Subtask #5
0 / 30.0

Subtask #6
0 / 13.0