Submission #49610

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
49610	2018-06-01T02:47:21 Z	Diuven	Circle selection (APIO18_circle_selection)	C++11	7 / 100	3000 ms	16556 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	484 KB	Output is correct
3	Correct	2 ms	484 KB	Output is correct
4	Correct	2 ms	484 KB	Output is correct
5	Correct	2 ms	484 KB	Output is correct
6	Correct	2 ms	484 KB	Output is correct
7	Correct	3 ms	484 KB	Output is correct
8	Correct	3 ms	484 KB	Output is correct
9	Correct	3 ms	540 KB	Output is correct
10	Correct	2 ms	556 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	2 ms	684 KB	Output is correct
15	Correct	2 ms	684 KB	Output is correct
16	Correct	2 ms	684 KB	Output is correct
17	Correct	2 ms	684 KB	Output is correct
18	Correct	2 ms	684 KB	Output is correct
19	Correct	5 ms	892 KB	Output is correct
20	Correct	5 ms	892 KB	Output is correct
21	Correct	5 ms	956 KB	Output is correct
22	Correct	143 ms	1092 KB	Output is correct
23	Correct	144 ms	1092 KB	Output is correct
24	Correct	156 ms	1092 KB	Output is correct
25	Correct	146 ms	1092 KB	Output is correct
26	Correct	190 ms	1092 KB	Output is correct

Subtask #2
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	223 ms	16152 KB	Output is correct
2	Correct	214 ms	16152 KB	Output is correct
3	Correct	209 ms	16464 KB	Output is correct
4	Correct	205 ms	16556 KB	Output is correct
5	Execution timed out	3063 ms	16556 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #3
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	16556 KB	Output is correct
2	Execution timed out	3057 ms	16556 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	3034 ms	16556 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	484 KB	Output is correct
3	Correct	2 ms	484 KB	Output is correct
4	Correct	2 ms	484 KB	Output is correct
5	Correct	2 ms	484 KB	Output is correct
6	Correct	2 ms	484 KB	Output is correct
7	Correct	3 ms	484 KB	Output is correct
8	Correct	3 ms	484 KB	Output is correct
9	Correct	3 ms	540 KB	Output is correct
10	Correct	2 ms	556 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	2 ms	684 KB	Output is correct
15	Correct	2 ms	684 KB	Output is correct
16	Correct	2 ms	684 KB	Output is correct
17	Correct	2 ms	684 KB	Output is correct
18	Correct	2 ms	684 KB	Output is correct
19	Correct	5 ms	892 KB	Output is correct
20	Correct	5 ms	892 KB	Output is correct
21	Correct	5 ms	956 KB	Output is correct
22	Correct	143 ms	1092 KB	Output is correct
23	Correct	144 ms	1092 KB	Output is correct
24	Correct	156 ms	1092 KB	Output is correct
25	Correct	146 ms	1092 KB	Output is correct
26	Correct	190 ms	1092 KB	Output is correct
27	Correct	13 ms	16556 KB	Output is correct
28	Correct	9 ms	16556 KB	Output is correct
29	Correct	14 ms	16556 KB	Output is correct
30	Correct	613 ms	16556 KB	Output is correct
31	Correct	567 ms	16556 KB	Output is correct
32	Correct	680 ms	16556 KB	Output is correct
33	Correct	71 ms	16556 KB	Output is correct
34	Correct	80 ms	16556 KB	Output is correct
35	Correct	81 ms	16556 KB	Output is correct
36	Execution timed out	3032 ms	16556 KB	Time limit exceeded
37	Halted	0 ms	0 KB	-

Subtask #6
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	484 KB	Output is correct
3	Correct	2 ms	484 KB	Output is correct
4	Correct	2 ms	484 KB	Output is correct
5	Correct	2 ms	484 KB	Output is correct
6	Correct	2 ms	484 KB	Output is correct
7	Correct	3 ms	484 KB	Output is correct
8	Correct	3 ms	484 KB	Output is correct
9	Correct	3 ms	540 KB	Output is correct
10	Correct	2 ms	556 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	2 ms	684 KB	Output is correct
15	Correct	2 ms	684 KB	Output is correct
16	Correct	2 ms	684 KB	Output is correct
17	Correct	2 ms	684 KB	Output is correct
18	Correct	2 ms	684 KB	Output is correct
19	Correct	5 ms	892 KB	Output is correct
20	Correct	5 ms	892 KB	Output is correct
21	Correct	5 ms	956 KB	Output is correct
22	Correct	143 ms	1092 KB	Output is correct
23	Correct	144 ms	1092 KB	Output is correct
24	Correct	156 ms	1092 KB	Output is correct
25	Correct	146 ms	1092 KB	Output is correct
26	Correct	190 ms	1092 KB	Output is correct
27	Correct	223 ms	16152 KB	Output is correct
28	Correct	214 ms	16152 KB	Output is correct
29	Correct	209 ms	16464 KB	Output is correct
30	Correct	205 ms	16556 KB	Output is correct
31	Execution timed out	3063 ms	16556 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

Submission #49610

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 0 / 12.0

Subtask #3 0 / 15.0

Subtask #4 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
0 / 15.0

Subtask #4
0 / 23.0

Subtask #5
0 / 30.0

Subtask #6
0 / 13.0