제출 #49610

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49610		Diuven	원 고르기 (APIO18_circle_selection)	C++11	7 / 100	3063 ms	16556 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int MX=300010, inf=2e9;

struct CIRCLE {
	int x, y, r, idx, kill;
} C[MX];

ll sq(ll x){ return x*x; }
ll dist(int a, int b){
	return sq(C[a].x-C[b].x)+sq(C[a].y-C[b].y);
}
bool hit(int a, int b){
	return dist(a,b)<=sq(C[a].r+C[b].r);
}

int n;

void input(){
	cin>>n;
	for(int i=1; i<=n; i++){
		int x, y, r;
		cin>>x>>y>>r;
		C[i]={x,y,r,i,0};
	}
}

vector<vector<vi>> G;
ll t=1<<30;
// [-t, 0), [0, t)

void init_grid(){
	vi X1, X2, X3, X4;
	for(int i=1; i<=n; i++){
		if(C[i].x<0){
			if(C[i].y<0) X3.push_back(i);
			else X2.push_back(i);
		}
		else{
			if(C[i].y<0) X4.push_back(i);
			else X1.push_back(i);
		}
	}
	vector<vi> A, B;
	if(!X3.empty()) A.push_back(X3);
	if(!X2.empty()) A.push_back(X2);
	if(!X4.empty()) B.push_back(X4);
	if(!X1.empty()) B.push_back(X1);

	if(!A.empty()) G.push_back(A);
	if(!B.empty()) G.push_back(B);
}

void resize_grid(){
	vector<vector<vi>> tmp;
	t/=2;
}

int range(ll x){
	if(x>0) return x/t;
	return -((-x+t-1)/t);
}

int range(const vi &cell){
	return range(cell.front());
}

int range(const vector<vi> &xrange){
	return range(xrange.front());
}

void process(const vi &cell, int killer){
	// cell을 업데이트 안해도 되나?
	for(int killed:cell)
		if(C[killed].kill==0 && hit(killed, killer))
			C[killed].kill=killer;
}

void kill(int idx){
	/*
	while(C[idx].r*2<t){
		resize_grid();
	}
	*/
	int x=C[idx].x, y=C[idx].y;
	ll lx=range(x)-2, hx=range(x)+3;
	ll ly=range(y)-2, hy=range(y)+3;
	
	int n1=G.size();
	int s1=0, e1=n1-1;
	while(s1<e1){
		int m1=(s1+e1)/2;
		if(range(G[m1])<lx) s1=m1+1;
		else e1=m1;
	}
	while(s1<n1 && lx<=range(G[s1]) && range(G[s1])<=hx){
		vector<vi> &X=G[s1];
		int n2=X.size();
		int s2=0, e2=n2-1;
		while(s2<e2){
			int m2=(s2+e2)/2;
			if(range(X[m2])<ly) s2=m2+1;
			else e2=m2;
		}
		while(s2<n2 && ly<=range(X[s2]) && range(X[s2])<=hy){
			process(X[s2], idx);
			s2++;
		}
		s1++;
	}
}

void solve(){
	CIRCLE D[MX];
	for(int i=1; i<=n; i++) D[i]=C[i];
	sort(D+1, D+n+1, [](CIRCLE &a, CIRCLE &b){
		if(a.r==b.r) return a.idx<b.idx;
		return a.r>b.r;
	});
	for(int i=1; i<=n; i++){
		int idx=D[i].idx;
		if(C[idx].kill!=0) continue;
		kill(idx);
	}
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	input();
	init_grid();
	solve();
	
	sort(C+1, C+n+1, [](CIRCLE &a, CIRCLE &b){ return a.idx<b.idx; });
	for(int i=1; i<=n; i++) cout<<C[i].kill<<' ';
	return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13