답안 #49338 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49338	2018-05-26T08:57:58 Z	WLZ	원 고르기 (APIO18_circle_selection)	C++17	7 / 100	3000 ms	8612 KB

circle_selection

#include <bits/stdc++.h>
using namespace std;

int n;
struct circle {
    int x, y, r, id;
			 
    circle() {
		x = y = r = id = 0;
	}
} arr[300005];
int ans[300005];

bool comp(const circle& a, const circle& b) {
	if (a.r == b.r) return a.id < b.id;
	return a.r > b.r;
}

bool inter(const circle& a, const circle& b) {
    long long dist = (a.x - b.x) * 1ll * (a.x - b.x) + (a.y - b.y) * 1ll * (a.y - b.y);
	return dist <= (a.r + b.r) * 1ll * (a.r + b.r);
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d %d", &arr[i].x, &arr[i].y, &arr[i].r);
		arr[i].id = i;
	}
	sort(arr + 1, arr + 1 + n, comp);
	for (int i = 1; i <= n; i++) ans[i] = i;
	for (int i = 1; i <= n; i++) {
		if (ans[arr[i].id] != arr[i].id) {
			continue;
		}
		for (int j = i + 1; j <= n; j++) {
			if (ans[arr[j].id] == arr[j].id) {
				if (inter(arr[i], arr[j])) {
					ans[arr[j].id] = arr[i].id;
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
	return 0;
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
circle_selection.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &arr[i].x, &arr[i].y, &arr[i].r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	4984 KB	Output is correct
2	Correct	7 ms	5096 KB	Output is correct
3	Correct	6 ms	5096 KB	Output is correct
4	Correct	8 ms	5096 KB	Output is correct
5	Correct	7 ms	5096 KB	Output is correct
6	Correct	8 ms	5172 KB	Output is correct
7	Correct	6 ms	5204 KB	Output is correct
8	Correct	7 ms	5204 KB	Output is correct
9	Correct	6 ms	5204 KB	Output is correct
10	Correct	6 ms	5204 KB	Output is correct
11	Correct	5 ms	5204 KB	Output is correct
12	Correct	5 ms	5204 KB	Output is correct
13	Correct	5 ms	5204 KB	Output is correct
14	Correct	6 ms	5204 KB	Output is correct
15	Correct	7 ms	5284 KB	Output is correct
16	Correct	7 ms	5284 KB	Output is correct
17	Correct	6 ms	5284 KB	Output is correct
18	Correct	6 ms	5284 KB	Output is correct
19	Correct	9 ms	5284 KB	Output is correct
20	Correct	10 ms	5348 KB	Output is correct
21	Correct	10 ms	5364 KB	Output is correct
22	Correct	38 ms	5364 KB	Output is correct
23	Correct	61 ms	5364 KB	Output is correct
24	Correct	44 ms	5364 KB	Output is correct
25	Correct	53 ms	5364 KB	Output is correct
26	Correct	37 ms	5364 KB	Output is correct

Subtask #2
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	216 ms	8612 KB	Output is correct
2	Correct	234 ms	8612 KB	Output is correct
3	Correct	237 ms	8612 KB	Output is correct
4	Correct	261 ms	8612 KB	Output is correct
5	Execution timed out	3043 ms	8612 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	8612 KB	Output is correct
2	Execution timed out	3009 ms	8612 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	3019 ms	8612 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	4984 KB	Output is correct
2	Correct	7 ms	5096 KB	Output is correct
3	Correct	6 ms	5096 KB	Output is correct
4	Correct	8 ms	5096 KB	Output is correct
5	Correct	7 ms	5096 KB	Output is correct
6	Correct	8 ms	5172 KB	Output is correct
7	Correct	6 ms	5204 KB	Output is correct
8	Correct	7 ms	5204 KB	Output is correct
9	Correct	6 ms	5204 KB	Output is correct
10	Correct	6 ms	5204 KB	Output is correct
11	Correct	5 ms	5204 KB	Output is correct
12	Correct	5 ms	5204 KB	Output is correct
13	Correct	5 ms	5204 KB	Output is correct
14	Correct	6 ms	5204 KB	Output is correct
15	Correct	7 ms	5284 KB	Output is correct
16	Correct	7 ms	5284 KB	Output is correct
17	Correct	6 ms	5284 KB	Output is correct
18	Correct	6 ms	5284 KB	Output is correct
19	Correct	9 ms	5284 KB	Output is correct
20	Correct	10 ms	5348 KB	Output is correct
21	Correct	10 ms	5364 KB	Output is correct
22	Correct	38 ms	5364 KB	Output is correct
23	Correct	61 ms	5364 KB	Output is correct
24	Correct	44 ms	5364 KB	Output is correct
25	Correct	53 ms	5364 KB	Output is correct
26	Correct	37 ms	5364 KB	Output is correct
27	Correct	15 ms	8612 KB	Output is correct
28	Correct	14 ms	8612 KB	Output is correct
29	Correct	12 ms	8612 KB	Output is correct
30	Correct	168 ms	8612 KB	Output is correct
31	Correct	145 ms	8612 KB	Output is correct
32	Correct	137 ms	8612 KB	Output is correct
33	Correct	84 ms	8612 KB	Output is correct
34	Correct	89 ms	8612 KB	Output is correct
35	Correct	85 ms	8612 KB	Output is correct
36	Execution timed out	3023 ms	8612 KB	Time limit exceeded
37	Halted	0 ms	0 KB	-

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	4984 KB	Output is correct
2	Correct	7 ms	5096 KB	Output is correct
3	Correct	6 ms	5096 KB	Output is correct
4	Correct	8 ms	5096 KB	Output is correct
5	Correct	7 ms	5096 KB	Output is correct
6	Correct	8 ms	5172 KB	Output is correct
7	Correct	6 ms	5204 KB	Output is correct
8	Correct	7 ms	5204 KB	Output is correct
9	Correct	6 ms	5204 KB	Output is correct
10	Correct	6 ms	5204 KB	Output is correct
11	Correct	5 ms	5204 KB	Output is correct
12	Correct	5 ms	5204 KB	Output is correct
13	Correct	5 ms	5204 KB	Output is correct
14	Correct	6 ms	5204 KB	Output is correct
15	Correct	7 ms	5284 KB	Output is correct
16	Correct	7 ms	5284 KB	Output is correct
17	Correct	6 ms	5284 KB	Output is correct
18	Correct	6 ms	5284 KB	Output is correct
19	Correct	9 ms	5284 KB	Output is correct
20	Correct	10 ms	5348 KB	Output is correct
21	Correct	10 ms	5364 KB	Output is correct
22	Correct	38 ms	5364 KB	Output is correct
23	Correct	61 ms	5364 KB	Output is correct
24	Correct	44 ms	5364 KB	Output is correct
25	Correct	53 ms	5364 KB	Output is correct
26	Correct	37 ms	5364 KB	Output is correct
27	Correct	216 ms	8612 KB	Output is correct
28	Correct	234 ms	8612 KB	Output is correct
29	Correct	237 ms	8612 KB	Output is correct
30	Correct	261 ms	8612 KB	Output is correct
31	Execution timed out	3043 ms	8612 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

답안 #49338

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