oj.uz

Submission #50800

# Submission time Handle Problem Language Result Execution time Memory
50800 2018-06-13T10:54:08 Z hamzqq9 Circle selection (APIO18_circle_selection) C++14
0 / 100
 717 ms 30880 KB 
#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 dec fdefwe
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-V[i][0].y%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-Now.y%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-T[now].y%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-b.x%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-T[now].y%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-C[i].y%R+C[i].y;

		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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 616 KB Output is correct
6 Correct 0 ms 616 KB Output is correct
7 Correct 3 ms 616 KB Output is correct
8 Correct 3 ms 616 KB Output is correct
9 Correct 3 ms 620 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 3 ms 620 KB Output is correct
12 Correct 4 ms 620 KB Output is correct
13 Incorrect 3 ms 620 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 27592 KB Output is correct
2 Correct 394 ms 27708 KB Output is correct
3 Correct 374 ms 27720 KB Output is correct
4 Correct 346 ms 27720 KB Output is correct
5 Incorrect 717 ms 27856 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 27856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 453 ms 30880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 616 KB Output is correct
6 Correct 0 ms 616 KB Output is correct
7 Correct 3 ms 616 KB Output is correct
8 Correct 3 ms 616 KB Output is correct
9 Correct 3 ms 620 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 3 ms 620 KB Output is correct
12 Correct 4 ms 620 KB Output is correct
13 Incorrect 3 ms 620 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 616 KB Output is correct
6 Correct 0 ms 616 KB Output is correct
7 Correct 3 ms 616 KB Output is correct
8 Correct 3 ms 616 KB Output is correct
9 Correct 3 ms 620 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 3 ms 620 KB Output is correct
12 Correct 4 ms 620 KB Output is correct
13 Incorrect 3 ms 620 KB Output isn't correct
14 Halted 0 ms 0 KB -