답안 #56901 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
56901	2018-07-13T06:37:57 Z	leejseo	원 고르기 (APIO18_circle_selection)	C++	7 / 100	172 ms	27108 KB

circle_selection

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

inline long long sq(long long x) { return x * x; }

typedef struct Circle{
	int x, y;
	int r;
	int i;
	Circle(int i_, int x_, int y_, int r_){ i = i_, x = x_, y = y_, r = r_; }
	bool meet(const Circle &c) const{
		return (sq((long long) (x - c.x)) + sq((long long) (y - c.y)) <= sq((long long) (r + c.r)));
	}
	bool operator < (const Circle &c) const{
		if (r != c.r) return r > c.r;
		return i < c.i;
	}
} Circle;

vector<Circle> L;
int ans[300000];
bool vis[300000];
int N;

int input(){
	scanf("%d", &N);
	int minr = 1<<30;
	int maxr = -1;
	bool ally0 = 1;
	int x, y, r;
	for (int i=0; i<N; i++){
		scanf("%d%d%d", &x, &y, &r);
		L.push_back(Circle(i, x, y, r));
		minr = min(minr, r);
		maxr = max(maxr, r);
		if (y != 0) ally0 = 0;
	}
	if (N <= 5000) return 1;
	if (ally0) return 2;
	if (minr == maxr) return 4;
	return 3; // we skip sub5/6 we assume sub3
}

void sub1(){
	sort(L.begin(), L.end());
	for (int i=0; i<N; i++){
		if (vis[i]) continue;
		int ind = L[i].i;
		ans[ind] = ind;
		vis[i] = 1;
		for (int j=0; j<N; j++){
			if (vis[j]) continue;
			if (L[i].meet(L[j])){
				ans[L[j].i] = ind;
				vis[j] = 1;
			}
		}
	}
}

int main(void){
	int st = input();
	if (st == 1){
		sub1();
		for (int i=0; i<N; i++){
			printf("%d ", ans[i]+1);
		}
		printf("\n");
	}
	else{
		printf("-1");
	}
}

Compilation message

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

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	616 KB	Output is correct
3	Correct	2 ms	736 KB	Output is correct
4	Correct	2 ms	736 KB	Output is correct
5	Correct	3 ms	736 KB	Output is correct
6	Correct	2 ms	736 KB	Output is correct
7	Correct	2 ms	768 KB	Output is correct
8	Correct	2 ms	772 KB	Output is correct
9	Correct	2 ms	772 KB	Output is correct
10	Correct	2 ms	896 KB	Output is correct
11	Correct	3 ms	896 KB	Output is correct
12	Correct	3 ms	896 KB	Output is correct
13	Correct	3 ms	896 KB	Output is correct
14	Correct	3 ms	896 KB	Output is correct
15	Correct	3 ms	896 KB	Output is correct
16	Correct	5 ms	916 KB	Output is correct
17	Correct	4 ms	916 KB	Output is correct
18	Correct	3 ms	932 KB	Output is correct
19	Correct	6 ms	1444 KB	Output is correct
20	Correct	7 ms	1544 KB	Output is correct
21	Correct	10 ms	1668 KB	Output is correct
22	Correct	70 ms	1924 KB	Output is correct
23	Correct	59 ms	1980 KB	Output is correct
24	Correct	56 ms	2260 KB	Output is correct
25	Correct	63 ms	2312 KB	Output is correct
26	Correct	59 ms	2540 KB	Output is correct

Subtask #2
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	172 ms	16624 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	16624 KB	Output is correct
2	Incorrect	101 ms	16624 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	160 ms	27108 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	616 KB	Output is correct
3	Correct	2 ms	736 KB	Output is correct
4	Correct	2 ms	736 KB	Output is correct
5	Correct	3 ms	736 KB	Output is correct
6	Correct	2 ms	736 KB	Output is correct
7	Correct	2 ms	768 KB	Output is correct
8	Correct	2 ms	772 KB	Output is correct
9	Correct	2 ms	772 KB	Output is correct
10	Correct	2 ms	896 KB	Output is correct
11	Correct	3 ms	896 KB	Output is correct
12	Correct	3 ms	896 KB	Output is correct
13	Correct	3 ms	896 KB	Output is correct
14	Correct	3 ms	896 KB	Output is correct
15	Correct	3 ms	896 KB	Output is correct
16	Correct	5 ms	916 KB	Output is correct
17	Correct	4 ms	916 KB	Output is correct
18	Correct	3 ms	932 KB	Output is correct
19	Correct	6 ms	1444 KB	Output is correct
20	Correct	7 ms	1544 KB	Output is correct
21	Correct	10 ms	1668 KB	Output is correct
22	Correct	70 ms	1924 KB	Output is correct
23	Correct	59 ms	1980 KB	Output is correct
24	Correct	56 ms	2260 KB	Output is correct
25	Correct	63 ms	2312 KB	Output is correct
26	Correct	59 ms	2540 KB	Output is correct
27	Incorrect	11 ms	27108 KB	Output isn't correct
28	Halted	0 ms	0 KB	-

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	616 KB	Output is correct
3	Correct	2 ms	736 KB	Output is correct
4	Correct	2 ms	736 KB	Output is correct
5	Correct	3 ms	736 KB	Output is correct
6	Correct	2 ms	736 KB	Output is correct
7	Correct	2 ms	768 KB	Output is correct
8	Correct	2 ms	772 KB	Output is correct
9	Correct	2 ms	772 KB	Output is correct
10	Correct	2 ms	896 KB	Output is correct
11	Correct	3 ms	896 KB	Output is correct
12	Correct	3 ms	896 KB	Output is correct
13	Correct	3 ms	896 KB	Output is correct
14	Correct	3 ms	896 KB	Output is correct
15	Correct	3 ms	896 KB	Output is correct
16	Correct	5 ms	916 KB	Output is correct
17	Correct	4 ms	916 KB	Output is correct
18	Correct	3 ms	932 KB	Output is correct
19	Correct	6 ms	1444 KB	Output is correct
20	Correct	7 ms	1544 KB	Output is correct
21	Correct	10 ms	1668 KB	Output is correct
22	Correct	70 ms	1924 KB	Output is correct
23	Correct	59 ms	1980 KB	Output is correct
24	Correct	56 ms	2260 KB	Output is correct
25	Correct	63 ms	2312 KB	Output is correct
26	Correct	59 ms	2540 KB	Output is correct
27	Incorrect	172 ms	16624 KB	Output isn't correct
28	Halted	0 ms	0 KB	-

답안 #56901

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