답안 #99833 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99833	2019-03-07T17:13:27 Z	TadijaSebez	원 고르기 (APIO18_circle_selection)	C++11	64 / 100	3000 ms	73180 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);}
bool operator < (circle a, circle b){ return a.r<b.r;}
const int N=300050;
const int mul=2e9+7;
circle a[N],b[N];
int ans[N];
unordered_map<ll,int> id;
vector<pair<int,int>> 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,b[i]=a[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;
   			if(!id[p]) id[p]=++cnt,all[cnt].clear();
   			all[id[p]].pb(mp(pa.second,a[i].id));
   		}
   		for(i=1;i<=cnt;i++) sort(all[i].begin(),all[i].end());
   		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++)
   			{
   				ll p=x+l;
   				if(!id.count(p)) continue;
   				int idx=id[p];
   				int lb=upper_bound(all[idx].begin(),all[idx].end(),mp(y-3,mul))-all[idx].begin();
   				//int rb=upper_bound(all[idx].begin(),all[idx].end(),mp(y+2,mul))-all[idx].begin();
   				for(int r=lb;r<all[idx].size() && all[idx][r]<=mp(y+2,mul);r++)
   				{
   					int c=all[idx][r].second;
   					if(!ans[c] && sec(b[c],a[i])) ans[c]=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:21:71: 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:35:57: 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:46:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        for(int r=lb;r<all[idx].size() && all[idx][r]<=mp(y+2,mul);r++)
                     ~^~~~~~~~~~~~~~~~
circle_selection.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
circle_selection.cpp:20:80: 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,b[i]=a[i];
                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	7424 KB	Output is correct
2	Correct	8 ms	7424 KB	Output is correct
3	Correct	7 ms	7424 KB	Output is correct
4	Correct	8 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	8 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	9 ms	7424 KB	Output is correct
12	Correct	9 ms	7424 KB	Output is correct
13	Correct	9 ms	7424 KB	Output is correct
14	Correct	11 ms	7424 KB	Output is correct
15	Correct	8 ms	7424 KB	Output is correct
16	Correct	9 ms	7424 KB	Output is correct
17	Correct	11 ms	7424 KB	Output is correct
18	Correct	10 ms	7424 KB	Output is correct
19	Correct	13 ms	7808 KB	Output is correct
20	Correct	13 ms	7808 KB	Output is correct
21	Correct	12 ms	7808 KB	Output is correct
22	Correct	32 ms	8192 KB	Output is correct
23	Correct	26 ms	8064 KB	Output is correct
24	Correct	25 ms	8320 KB	Output is correct
25	Correct	25 ms	8320 KB	Output is correct
26	Correct	26 ms	8448 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	408 ms	31968 KB	Output is correct
2	Correct	501 ms	34324 KB	Output is correct
3	Correct	479 ms	33056 KB	Output is correct
4	Correct	380 ms	32740 KB	Output is correct
5	Correct	1102 ms	48720 KB	Output is correct
6	Correct	1572 ms	65956 KB	Output is correct
7	Correct	1221 ms	51832 KB	Output is correct
8	Correct	1332 ms	59664 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	7424 KB	Output is correct
2	Correct	383 ms	21972 KB	Output is correct
3	Correct	1512 ms	56676 KB	Output is correct
4	Correct	1517 ms	57856 KB	Output is correct
5	Correct	1141 ms	50772 KB	Output is correct
6	Correct	541 ms	30504 KB	Output is correct
7	Correct	267 ms	19940 KB	Output is correct
8	Correct	62 ms	10488 KB	Output is correct
9	Correct	1309 ms	55024 KB	Output is correct
10	Correct	961 ms	47068 KB	Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	7424 KB	Output is correct
2	Correct	8 ms	7424 KB	Output is correct
3	Correct	7 ms	7424 KB	Output is correct
4	Correct	8 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	8 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	9 ms	7424 KB	Output is correct
12	Correct	9 ms	7424 KB	Output is correct
13	Correct	9 ms	7424 KB	Output is correct
14	Correct	11 ms	7424 KB	Output is correct
15	Correct	8 ms	7424 KB	Output is correct
16	Correct	9 ms	7424 KB	Output is correct
17	Correct	11 ms	7424 KB	Output is correct
18	Correct	10 ms	7424 KB	Output is correct
19	Correct	13 ms	7808 KB	Output is correct
20	Correct	13 ms	7808 KB	Output is correct
21	Correct	12 ms	7808 KB	Output is correct
22	Correct	32 ms	8192 KB	Output is correct
23	Correct	26 ms	8064 KB	Output is correct
24	Correct	25 ms	8320 KB	Output is correct
25	Correct	25 ms	8320 KB	Output is correct
26	Correct	26 ms	8448 KB	Output is correct
27	Correct	18 ms	8448 KB	Output is correct
28	Correct	19 ms	8320 KB	Output is correct
29	Correct	18 ms	8320 KB	Output is correct
30	Correct	39 ms	8824 KB	Output is correct
31	Correct	40 ms	9208 KB	Output is correct
32	Correct	37 ms	9080 KB	Output is correct
33	Correct	100 ms	15596 KB	Output is correct
34	Correct	101 ms	15596 KB	Output is correct
35	Correct	127 ms	16108 KB	Output is correct
36	Correct	420 ms	25828 KB	Output is correct
37	Correct	454 ms	25424 KB	Output is correct
38	Correct	388 ms	23920 KB	Output is correct
39	Correct	582 ms	19436 KB	Output is correct
40	Correct	529 ms	19736 KB	Output is correct
41	Correct	576 ms	19504 KB	Output is correct
42	Correct	393 ms	19128 KB	Output is correct
43	Correct	660 ms	29660 KB	Output is correct
44	Correct	641 ms	30052 KB	Output is correct
45	Correct	632 ms	29636 KB	Output is correct
46	Correct	630 ms	29636 KB	Output is correct
47	Correct	637 ms	29680 KB	Output is correct
48	Correct	569 ms	29728 KB	Output is correct
49	Correct	643 ms	29944 KB	Output is correct
50	Correct	640 ms	29484 KB	Output is correct

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	7424 KB	Output is correct
2	Correct	8 ms	7424 KB	Output is correct
3	Correct	7 ms	7424 KB	Output is correct
4	Correct	8 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	8 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	9 ms	7424 KB	Output is correct
12	Correct	9 ms	7424 KB	Output is correct
13	Correct	9 ms	7424 KB	Output is correct
14	Correct	11 ms	7424 KB	Output is correct
15	Correct	8 ms	7424 KB	Output is correct
16	Correct	9 ms	7424 KB	Output is correct
17	Correct	11 ms	7424 KB	Output is correct
18	Correct	10 ms	7424 KB	Output is correct
19	Correct	13 ms	7808 KB	Output is correct
20	Correct	13 ms	7808 KB	Output is correct
21	Correct	12 ms	7808 KB	Output is correct
22	Correct	32 ms	8192 KB	Output is correct
23	Correct	26 ms	8064 KB	Output is correct
24	Correct	25 ms	8320 KB	Output is correct
25	Correct	25 ms	8320 KB	Output is correct
26	Correct	26 ms	8448 KB	Output is correct
27	Correct	408 ms	31968 KB	Output is correct
28	Correct	501 ms	34324 KB	Output is correct
29	Correct	479 ms	33056 KB	Output is correct
30	Correct	380 ms	32740 KB	Output is correct
31	Correct	1102 ms	48720 KB	Output is correct
32	Correct	1572 ms	65956 KB	Output is correct
33	Correct	1221 ms	51832 KB	Output is correct
34	Correct	1332 ms	59664 KB	Output is correct
35	Correct	10 ms	7424 KB	Output is correct
36	Correct	383 ms	21972 KB	Output is correct
37	Correct	1512 ms	56676 KB	Output is correct
38	Correct	1517 ms	57856 KB	Output is correct
39	Correct	1141 ms	50772 KB	Output is correct
40	Correct	541 ms	30504 KB	Output is correct
41	Correct	267 ms	19940 KB	Output is correct
42	Correct	62 ms	10488 KB	Output is correct
43	Correct	1309 ms	55024 KB	Output is correct
44	Correct	961 ms	47068 KB	Output is correct
45	Correct	1671 ms	56512 KB	Output is correct
46	Execution timed out	3067 ms	73180 KB	Time limit exceeded
47	Halted	0 ms	0 KB	-

답안 #99833

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 12.0 / 12.0

Subtask #3 15.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
15.0 / 15.0

Subtask #4
0 / 23.0

Subtask #5
30.0 / 30.0

Subtask #6
0 / 13.0