Submission #932359

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
932359	2024-02-23T08:46:58 Z	siewjh	Circle selection (APIO18_circle_selection)	C++17	7 / 100	254 ms	25196 KB

circle_selection

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 5005;
int ans[MAXN];
ll xv[MAXN], yv[MAXN], rv[MAXN];
bool die[MAXN], cross[MAXN][MAXN];
ll sq(ll x){
	return x * x;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int nums; cin >> nums;
	for (int i = 0; i < nums; i++) cin >> xv[i] >> yv[i] >> rv[i];
	for (int i = 0; i < nums; i++){
		cross[i][i] = 1;
		for (int j = i + 1; j < nums; j++) cross[i][j] = cross[j][i] = ((sq(xv[i] - xv[j]) + sq(yv[i] - yv[j])) <= sq(rv[i] + rv[j]));
	}
	while (true){
		int ind = -1; ll sz = 0;
		for (int i = 0; i < nums; i++)
			if (!die[i] && rv[i] > sz){
				sz = rv[i];
				ind = i;
			}
		if (ind == -1) break;
		for (int i = 0; i < nums; i++)
			if (!die[i] && cross[i][ind]){
				ans[i] = ind + 1;
				die[i] = 1;
			}
	}
	for (int i = 0; i < nums; i++) cout << ans[i] << ' ';
}

Subtask #1

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	464 KB	Output is correct
6	Correct	1 ms	2648 KB	Output is correct
7	Correct	1 ms	2652 KB	Output is correct
8	Correct	1 ms	2516 KB	Output is correct
9	Correct	2 ms	2652 KB	Output is correct
10	Correct	1 ms	2508 KB	Output is correct
11	Correct	1 ms	2652 KB	Output is correct
12	Correct	1 ms	2652 KB	Output is correct
13	Correct	1 ms	2652 KB	Output is correct
14	Correct	1 ms	2480 KB	Output is correct
15	Correct	1 ms	2652 KB	Output is correct
16	Correct	2 ms	6868 KB	Output is correct
17	Correct	2 ms	6748 KB	Output is correct
18	Correct	3 ms	6880 KB	Output is correct
19	Correct	47 ms	24996 KB	Output is correct
20	Correct	45 ms	25168 KB	Output is correct
21	Correct	45 ms	25176 KB	Output is correct
22	Correct	249 ms	25192 KB	Output is correct
23	Correct	221 ms	25196 KB	Output is correct
24	Correct	225 ms	25172 KB	Output is correct
25	Correct	227 ms	25136 KB	Output is correct
26	Correct	254 ms	25196 KB	Output is correct

Subtask #2

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	3 ms	1112 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Runtime error	3 ms	1116 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #4

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	3 ms	1116 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	464 KB	Output is correct
6	Correct	1 ms	2648 KB	Output is correct
7	Correct	1 ms	2652 KB	Output is correct
8	Correct	1 ms	2516 KB	Output is correct
9	Correct	2 ms	2652 KB	Output is correct
10	Correct	1 ms	2508 KB	Output is correct
11	Correct	1 ms	2652 KB	Output is correct
12	Correct	1 ms	2652 KB	Output is correct
13	Correct	1 ms	2652 KB	Output is correct
14	Correct	1 ms	2480 KB	Output is correct
15	Correct	1 ms	2652 KB	Output is correct
16	Correct	2 ms	6868 KB	Output is correct
17	Correct	2 ms	6748 KB	Output is correct
18	Correct	3 ms	6880 KB	Output is correct
19	Correct	47 ms	24996 KB	Output is correct
20	Correct	45 ms	25168 KB	Output is correct
21	Correct	45 ms	25176 KB	Output is correct
22	Correct	249 ms	25192 KB	Output is correct
23	Correct	221 ms	25196 KB	Output is correct
24	Correct	225 ms	25172 KB	Output is correct
25	Correct	227 ms	25136 KB	Output is correct
26	Correct	254 ms	25196 KB	Output is correct
27	Runtime error	3 ms	1048 KB	Execution killed with signal 11
28	Halted	0 ms	0 KB	-

Subtask #6

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	464 KB	Output is correct
6	Correct	1 ms	2648 KB	Output is correct
7	Correct	1 ms	2652 KB	Output is correct
8	Correct	1 ms	2516 KB	Output is correct
9	Correct	2 ms	2652 KB	Output is correct
10	Correct	1 ms	2508 KB	Output is correct
11	Correct	1 ms	2652 KB	Output is correct
12	Correct	1 ms	2652 KB	Output is correct
13	Correct	1 ms	2652 KB	Output is correct
14	Correct	1 ms	2480 KB	Output is correct
15	Correct	1 ms	2652 KB	Output is correct
16	Correct	2 ms	6868 KB	Output is correct
17	Correct	2 ms	6748 KB	Output is correct
18	Correct	3 ms	6880 KB	Output is correct
19	Correct	47 ms	24996 KB	Output is correct
20	Correct	45 ms	25168 KB	Output is correct
21	Correct	45 ms	25176 KB	Output is correct
22	Correct	249 ms	25192 KB	Output is correct
23	Correct	221 ms	25196 KB	Output is correct
24	Correct	225 ms	25172 KB	Output is correct
25	Correct	227 ms	25136 KB	Output is correct
26	Correct	254 ms	25196 KB	Output is correct
27	Runtime error	3 ms	1112 KB	Execution killed with signal 11
28	Halted	0 ms	0 KB	-