답안 #99822 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99822	2019-03-07T16:29:06 Z	TadijaSebez	원 고르기 (APIO18_circle_selection)	C++11	49 / 100	3000 ms	217484 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;
const ll mul=2e9+7;
circle a[N];
int ans[N];
unordered_map<ll,int> id;
vector<circle> all[N];
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;
		id.clear();
		int cnt=0;
		for(i=1;i<=n;i++) if(!ans[a[i].id])
		{
			pair<int,int> pa=mp(floor((double)a[i].x/po),floor((double)a[i].y/po));
			ll p=pa.first*mul+pa.second;
			if(!id[p]) id[p]=++cnt,all[cnt].clear();
			all[id[p]].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++)
			{
				int idx=id[(x+l)*mul+y+r];
				if(!idx) continue;
				vector<circle> v=all[idx],e;
				for(circle c:v)
				{
					if(sec(c,a[i])) ans[c.id]=a[i].id;
					else e.pb(c);
				}
				all[idx]=e;
			}
		}
	}
	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:20: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:33: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:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
circle_selection.cpp:19: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	10 ms	7424 KB	Output is correct
2	Correct	9 ms	7424 KB	Output is correct
3	Correct	11 ms	7368 KB	Output is correct
4	Correct	9 ms	7424 KB	Output is correct
5	Correct	8 ms	7424 KB	Output is correct
6	Correct	9 ms	7424 KB	Output is correct
7	Correct	9 ms	7424 KB	Output is correct
8	Correct	9 ms	7424 KB	Output is correct
9	Correct	9 ms	7424 KB	Output is correct
10	Correct	9 ms	7424 KB	Output is correct
11	Correct	10 ms	7424 KB	Output is correct
12	Correct	10 ms	7424 KB	Output is correct
13	Correct	8 ms	7424 KB	Output is correct
14	Correct	10 ms	7504 KB	Output is correct
15	Correct	11 ms	7424 KB	Output is correct
16	Correct	10 ms	7552 KB	Output is correct
17	Correct	10 ms	7524 KB	Output is correct
18	Correct	9 ms	7424 KB	Output is correct
19	Correct	13 ms	7936 KB	Output is correct
20	Correct	14 ms	8060 KB	Output is correct
21	Correct	13 ms	7936 KB	Output is correct
22	Correct	47 ms	11812 KB	Output is correct
23	Correct	41 ms	11940 KB	Output is correct
24	Correct	47 ms	10788 KB	Output is correct
25	Correct	62 ms	10816 KB	Output is correct
26	Correct	53 ms	11612 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	358 ms	33740 KB	Output is correct
2	Correct	407 ms	44580 KB	Output is correct
3	Correct	407 ms	39632 KB	Output is correct
4	Correct	365 ms	38104 KB	Output is correct
5	Correct	779 ms	96544 KB	Output is correct
6	Correct	2084 ms	161732 KB	Output is correct
7	Correct	877 ms	106904 KB	Output is correct
8	Correct	1265 ms	135584 KB	Output is correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	7424 KB	Output is correct
2	Correct	1660 ms	86956 KB	Output is correct
3	Execution timed out	3057 ms	217484 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

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

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	7424 KB	Output is correct
2	Correct	9 ms	7424 KB	Output is correct
3	Correct	11 ms	7368 KB	Output is correct
4	Correct	9 ms	7424 KB	Output is correct
5	Correct	8 ms	7424 KB	Output is correct
6	Correct	9 ms	7424 KB	Output is correct
7	Correct	9 ms	7424 KB	Output is correct
8	Correct	9 ms	7424 KB	Output is correct
9	Correct	9 ms	7424 KB	Output is correct
10	Correct	9 ms	7424 KB	Output is correct
11	Correct	10 ms	7424 KB	Output is correct
12	Correct	10 ms	7424 KB	Output is correct
13	Correct	8 ms	7424 KB	Output is correct
14	Correct	10 ms	7504 KB	Output is correct
15	Correct	11 ms	7424 KB	Output is correct
16	Correct	10 ms	7552 KB	Output is correct
17	Correct	10 ms	7524 KB	Output is correct
18	Correct	9 ms	7424 KB	Output is correct
19	Correct	13 ms	7936 KB	Output is correct
20	Correct	14 ms	8060 KB	Output is correct
21	Correct	13 ms	7936 KB	Output is correct
22	Correct	47 ms	11812 KB	Output is correct
23	Correct	41 ms	11940 KB	Output is correct
24	Correct	47 ms	10788 KB	Output is correct
25	Correct	62 ms	10816 KB	Output is correct
26	Correct	53 ms	11612 KB	Output is correct
27	Correct	19 ms	8440 KB	Output is correct
28	Correct	18 ms	8532 KB	Output is correct
29	Correct	18 ms	8412 KB	Output is correct
30	Correct	89 ms	16336 KB	Output is correct
31	Correct	86 ms	16208 KB	Output is correct
32	Correct	71 ms	14068 KB	Output is correct
33	Correct	114 ms	17252 KB	Output is correct
34	Correct	122 ms	17380 KB	Output is correct
35	Correct	150 ms	18780 KB	Output is correct
36	Correct	1888 ms	91972 KB	Output is correct
37	Correct	1775 ms	90816 KB	Output is correct
38	Correct	1659 ms	90684 KB	Output is correct
39	Correct	682 ms	43196 KB	Output is correct
40	Correct	991 ms	43208 KB	Output is correct
41	Correct	761 ms	44404 KB	Output is correct
42	Correct	462 ms	40736 KB	Output is correct
43	Correct	2388 ms	144924 KB	Output is correct
44	Correct	2207 ms	146076 KB	Output is correct
45	Correct	2174 ms	144816 KB	Output is correct
46	Correct	2154 ms	144244 KB	Output is correct
47	Correct	2172 ms	144612 KB	Output is correct
48	Correct	2126 ms	145572 KB	Output is correct
49	Correct	2154 ms	145132 KB	Output is correct
50	Correct	2261 ms	144460 KB	Output is correct

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	7424 KB	Output is correct
2	Correct	9 ms	7424 KB	Output is correct
3	Correct	11 ms	7368 KB	Output is correct
4	Correct	9 ms	7424 KB	Output is correct
5	Correct	8 ms	7424 KB	Output is correct
6	Correct	9 ms	7424 KB	Output is correct
7	Correct	9 ms	7424 KB	Output is correct
8	Correct	9 ms	7424 KB	Output is correct
9	Correct	9 ms	7424 KB	Output is correct
10	Correct	9 ms	7424 KB	Output is correct
11	Correct	10 ms	7424 KB	Output is correct
12	Correct	10 ms	7424 KB	Output is correct
13	Correct	8 ms	7424 KB	Output is correct
14	Correct	10 ms	7504 KB	Output is correct
15	Correct	11 ms	7424 KB	Output is correct
16	Correct	10 ms	7552 KB	Output is correct
17	Correct	10 ms	7524 KB	Output is correct
18	Correct	9 ms	7424 KB	Output is correct
19	Correct	13 ms	7936 KB	Output is correct
20	Correct	14 ms	8060 KB	Output is correct
21	Correct	13 ms	7936 KB	Output is correct
22	Correct	47 ms	11812 KB	Output is correct
23	Correct	41 ms	11940 KB	Output is correct
24	Correct	47 ms	10788 KB	Output is correct
25	Correct	62 ms	10816 KB	Output is correct
26	Correct	53 ms	11612 KB	Output is correct
27	Correct	358 ms	33740 KB	Output is correct
28	Correct	407 ms	44580 KB	Output is correct
29	Correct	407 ms	39632 KB	Output is correct
30	Correct	365 ms	38104 KB	Output is correct
31	Correct	779 ms	96544 KB	Output is correct
32	Correct	2084 ms	161732 KB	Output is correct
33	Correct	877 ms	106904 KB	Output is correct
34	Correct	1265 ms	135584 KB	Output is correct
35	Correct	9 ms	7424 KB	Output is correct
36	Correct	1660 ms	86956 KB	Output is correct
37	Execution timed out	3057 ms	217484 KB	Time limit exceeded
38	Halted	0 ms	0 KB	-

답안 #99822

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