제출 #50801

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
50801		hamzqq9	원 고르기 (APIO18_circle_selection)	C++14	45 / 100	1553 ms	75932 KiB

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]);

}

컴파일 시 표준 에러 (stderr) 메시지

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 / 7
• Subtask 2: 0 / 12
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13