Submission #982259

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
982259	2024-05-14T04:57:55 Z	Jawad_Akbar_JJ	Circle selection (APIO18_circle_selection)	C++17	7 / 100	232 ms	7552 KB

circle_selection

#include <iostream>
#include <set>

using namespace std;
#define int long long

const int N = 3e5 + 10;

int x[N];
int y[N];
int r[N];

int erased[N];

int dist(int i,int j){
	int xd = x[i] - x[j];
	int yd = y[i] - y[j];
	return xd * xd + yd * yd;
}

void sub1(int n){
	set<pair<int,int>> s;

	for (int i=1;i<=n;i++)
		s.insert({-r[i],i});

	while (s.size() > 0){
		int i = (*begin(s)).second;
		for (int j=1;j<=n;j++)
			if (!erased[j] and dist(i,j) <= (r[i] + r[j]) * (r[i] + r[j])){
				s.erase({-r[j],j});
				erased[j] = i;
			}
	}
	for (int i=1;i<=n;i++)
		cout<<erased[i]<<' ';
	cout<<'\n';
	exit(0);
}

signed main(){
	int n;
	cin>>n;

	for (int i=1;i<=n;i++)
		cin>>x[i]>>y[i]>>r[i];
	

	if (n <= 5000)
		sub1(n);


}

// 11
// 9 9 2
// 13 2 1
// 11 8 2
// 3 3 2
// 3 12 1
// 12 14 1
// 9 8 5
// 2 8 2
// 5 2 1
// 14 4 2
// 14 14 1

Subtask #1

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6492 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	1 ms	6492 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	1 ms	6492 KB	Output is correct
6	Correct	1 ms	6648 KB	Output is correct
7	Correct	2 ms	6492 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	1 ms	6492 KB	Output is correct
10	Correct	1 ms	6492 KB	Output is correct
11	Correct	1 ms	6492 KB	Output is correct
12	Correct	1 ms	6492 KB	Output is correct
13	Correct	1 ms	6492 KB	Output is correct
14	Correct	1 ms	6492 KB	Output is correct
15	Correct	1 ms	6492 KB	Output is correct
16	Correct	2 ms	6748 KB	Output is correct
17	Correct	2 ms	6492 KB	Output is correct
18	Correct	2 ms	6492 KB	Output is correct
19	Correct	7 ms	6748 KB	Output is correct
20	Correct	7 ms	6748 KB	Output is correct
21	Correct	7 ms	6744 KB	Output is correct
22	Correct	44 ms	6928 KB	Output is correct
23	Correct	45 ms	6748 KB	Output is correct
24	Correct	45 ms	6924 KB	Output is correct
25	Correct	44 ms	6936 KB	Output is correct
26	Correct	45 ms	6944 KB	Output is correct

Subtask #2

0 / 12.0

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

Subtask #3

0 / 15.0

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

Subtask #4

0 / 23.0

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

Subtask #5

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6492 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	1 ms	6492 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	1 ms	6492 KB	Output is correct
6	Correct	1 ms	6648 KB	Output is correct
7	Correct	2 ms	6492 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	1 ms	6492 KB	Output is correct
10	Correct	1 ms	6492 KB	Output is correct
11	Correct	1 ms	6492 KB	Output is correct
12	Correct	1 ms	6492 KB	Output is correct
13	Correct	1 ms	6492 KB	Output is correct
14	Correct	1 ms	6492 KB	Output is correct
15	Correct	1 ms	6492 KB	Output is correct
16	Correct	2 ms	6748 KB	Output is correct
17	Correct	2 ms	6492 KB	Output is correct
18	Correct	2 ms	6492 KB	Output is correct
19	Correct	7 ms	6748 KB	Output is correct
20	Correct	7 ms	6748 KB	Output is correct
21	Correct	7 ms	6744 KB	Output is correct
22	Correct	44 ms	6928 KB	Output is correct
23	Correct	45 ms	6748 KB	Output is correct
24	Correct	45 ms	6924 KB	Output is correct
25	Correct	44 ms	6936 KB	Output is correct
26	Correct	45 ms	6944 KB	Output is correct
27	Incorrect	10 ms	6488 KB	Output isn't correct
28	Halted	0 ms	0 KB	-

Subtask #6

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6492 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	1 ms	6492 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	1 ms	6492 KB	Output is correct
6	Correct	1 ms	6648 KB	Output is correct
7	Correct	2 ms	6492 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	1 ms	6492 KB	Output is correct
10	Correct	1 ms	6492 KB	Output is correct
11	Correct	1 ms	6492 KB	Output is correct
12	Correct	1 ms	6492 KB	Output is correct
13	Correct	1 ms	6492 KB	Output is correct
14	Correct	1 ms	6492 KB	Output is correct
15	Correct	1 ms	6492 KB	Output is correct
16	Correct	2 ms	6748 KB	Output is correct
17	Correct	2 ms	6492 KB	Output is correct
18	Correct	2 ms	6492 KB	Output is correct
19	Correct	7 ms	6748 KB	Output is correct
20	Correct	7 ms	6748 KB	Output is correct
21	Correct	7 ms	6744 KB	Output is correct
22	Correct	44 ms	6928 KB	Output is correct
23	Correct	45 ms	6748 KB	Output is correct
24	Correct	45 ms	6924 KB	Output is correct
25	Correct	44 ms	6936 KB	Output is correct
26	Correct	45 ms	6944 KB	Output is correct
27	Incorrect	204 ms	7480 KB	Output isn't correct
28	Halted	0 ms	0 KB	-