답안 #99819 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99819	2019-03-07T16:15:40 Z	TadijaSebez	원 고르기 (APIO18_circle_selection)	C++11	49 / 100	3000 ms	182620 KB

circle_selection

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
struct circle{ ll x,y,r;int id;circle(){}circle(ll a, ll b, ll c):x(a),y(b),r(c){}};
ll sq(ll x){ return x*x;}
bool sec(circle a, circle b){ return sq(a.x-b.x)+sq(a.y-b.y)<=sq(a.r+b.r);}
const int N=300050;
circle a[N];
int ans[N];
map<pair<int,int>,vector<circle>> all;
int main()
{
	int n,i;
	scanf("%i",&n);
	for(i=1;i<=n;i++) scanf("%lld %lld %lld",&a[i].x,&a[i].y,&a[i].r),a[i].id=i;
	sort(a+1,a+1+n,[](circle a, circle b){ return a.r>b.r || a.r==b.r && a.id<b.id;});
	for(int j=30;j>=0;j--)
	{
		int po=1<<j;
		all.clear();
		for(i=1;i<=n;i++) if(!ans[a[i].id])
		{
			all[mp(floor((double)a[i].x/po),floor((double)a[i].y/po))].pb(a[i]);
		}
		for(i=1;i<=n;i++) if(!ans[a[i].id] && a[i].r>=(1<<j-1))
		{
			int x=floor((double)a[i].x/po);
			int y=floor((double)a[i].y/po);
			for(int l=-2;l<=2;l++) for(int r=-2;r<=2;r++)
			{
				vector<circle> v=all[mp(x+l,y+r)];
				for(circle c:v) if(!ans[c.id] && sec(c,a[i])) ans[c.id]=a[i].id;
			}
		}
	}
	for(i=1;i<=n;i++) printf("%i%c",ans[i],i==n?'\n':' ');
	return 0;
}

Compilation message

circle_selection.cpp: In lambda function:
circle_selection.cpp:18:68: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  sort(a+1,a+1+n,[](circle a, circle b){ return a.r>b.r || a.r==b.r && a.id<b.id;});
                                                           ~~~~~~~~~^~~~~~~~~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:27:54: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   for(i=1;i<=n;i++) if(!ans[a[i].id] && a[i].r>=(1<<j-1))
                                                     ~^~
circle_selection.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
circle_selection.cpp:17:67: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1;i<=n;i++) scanf("%lld %lld %lld",&a[i].x,&a[i].y,&a[i].r),a[i].id=i;
                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	3 ms	256 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	3 ms	256 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	4 ms	384 KB	Output is correct
12	Correct	3 ms	512 KB	Output is correct
13	Correct	4 ms	512 KB	Output is correct
14	Correct	3 ms	384 KB	Output is correct
15	Correct	4 ms	404 KB	Output is correct
16	Correct	3 ms	512 KB	Output is correct
17	Correct	4 ms	384 KB	Output is correct
18	Correct	4 ms	512 KB	Output is correct
19	Correct	8 ms	1024 KB	Output is correct
20	Correct	8 ms	1276 KB	Output is correct
21	Correct	8 ms	996 KB	Output is correct
22	Correct	59 ms	5192 KB	Output is correct
23	Correct	78 ms	5452 KB	Output is correct
24	Correct	54 ms	4424 KB	Output is correct
25	Correct	74 ms	5084 KB	Output is correct
26	Correct	60 ms	5276 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	349 ms	29804 KB	Output is correct
2	Correct	399 ms	29308 KB	Output is correct
3	Correct	471 ms	39468 KB	Output is correct
4	Correct	366 ms	37724 KB	Output is correct
5	Correct	928 ms	40284 KB	Output is correct
6	Correct	2976 ms	79716 KB	Output is correct
7	Correct	986 ms	40404 KB	Output is correct
8	Correct	1535 ms	45084 KB	Output is correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2751 ms	90640 KB	Output is correct
3	Execution timed out	3015 ms	56176 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

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

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	3 ms	256 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	3 ms	256 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	4 ms	384 KB	Output is correct
12	Correct	3 ms	512 KB	Output is correct
13	Correct	4 ms	512 KB	Output is correct
14	Correct	3 ms	384 KB	Output is correct
15	Correct	4 ms	404 KB	Output is correct
16	Correct	3 ms	512 KB	Output is correct
17	Correct	4 ms	384 KB	Output is correct
18	Correct	4 ms	512 KB	Output is correct
19	Correct	8 ms	1024 KB	Output is correct
20	Correct	8 ms	1276 KB	Output is correct
21	Correct	8 ms	996 KB	Output is correct
22	Correct	59 ms	5192 KB	Output is correct
23	Correct	78 ms	5452 KB	Output is correct
24	Correct	54 ms	4424 KB	Output is correct
25	Correct	74 ms	5084 KB	Output is correct
26	Correct	60 ms	5276 KB	Output is correct
27	Correct	15 ms	1996 KB	Output is correct
28	Correct	12 ms	1792 KB	Output is correct
29	Correct	12 ms	1852 KB	Output is correct
30	Correct	144 ms	11292 KB	Output is correct
31	Correct	136 ms	11148 KB	Output is correct
32	Correct	147 ms	8616 KB	Output is correct
33	Correct	101 ms	13516 KB	Output is correct
34	Correct	94 ms	13284 KB	Output is correct
35	Correct	113 ms	13104 KB	Output is correct
36	Correct	2869 ms	100868 KB	Output is correct
37	Correct	2771 ms	89312 KB	Output is correct
38	Correct	2791 ms	102552 KB	Output is correct
39	Correct	883 ms	16300 KB	Output is correct
40	Correct	902 ms	16604 KB	Output is correct
41	Correct	956 ms	16324 KB	Output is correct
42	Correct	658 ms	15260 KB	Output is correct
43	Correct	2366 ms	182060 KB	Output is correct
44	Correct	2174 ms	182208 KB	Output is correct
45	Correct	2230 ms	182032 KB	Output is correct
46	Correct	2235 ms	182528 KB	Output is correct
47	Correct	2227 ms	182620 KB	Output is correct
48	Correct	2195 ms	182448 KB	Output is correct
49	Correct	2088 ms	182596 KB	Output is correct
50	Correct	2142 ms	182484 KB	Output is correct

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	3 ms	256 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	3 ms	256 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	4 ms	384 KB	Output is correct
12	Correct	3 ms	512 KB	Output is correct
13	Correct	4 ms	512 KB	Output is correct
14	Correct	3 ms	384 KB	Output is correct
15	Correct	4 ms	404 KB	Output is correct
16	Correct	3 ms	512 KB	Output is correct
17	Correct	4 ms	384 KB	Output is correct
18	Correct	4 ms	512 KB	Output is correct
19	Correct	8 ms	1024 KB	Output is correct
20	Correct	8 ms	1276 KB	Output is correct
21	Correct	8 ms	996 KB	Output is correct
22	Correct	59 ms	5192 KB	Output is correct
23	Correct	78 ms	5452 KB	Output is correct
24	Correct	54 ms	4424 KB	Output is correct
25	Correct	74 ms	5084 KB	Output is correct
26	Correct	60 ms	5276 KB	Output is correct
27	Correct	349 ms	29804 KB	Output is correct
28	Correct	399 ms	29308 KB	Output is correct
29	Correct	471 ms	39468 KB	Output is correct
30	Correct	366 ms	37724 KB	Output is correct
31	Correct	928 ms	40284 KB	Output is correct
32	Correct	2976 ms	79716 KB	Output is correct
33	Correct	986 ms	40404 KB	Output is correct
34	Correct	1535 ms	45084 KB	Output is correct
35	Correct	2 ms	384 KB	Output is correct
36	Correct	2751 ms	90640 KB	Output is correct
37	Execution timed out	3015 ms	56176 KB	Time limit exceeded
38	Halted	0 ms	0 KB	-

답안 #99819

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 12.0 / 12.0

Subtask #3 0 / 15.0

Subtask #4 0 / 23.0

Subtask #5 30.0 / 30.0

Subtask #6 0 / 13.0

Subtask #1
7.0 / 7.0

Subtask #2
12.0 / 12.0

Subtask #3
0 / 15.0

Subtask #4
0 / 23.0

Subtask #5
30.0 / 30.0

Subtask #6
0 / 13.0