답안 #99823 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99823	2019-03-07T16:31:46 Z	TadijaSebez	원 고르기 (APIO18_circle_selection)	C++11	49 / 100	3000 ms	140392 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++)
			{
				ll p=(x+l)*mul+y+r;
				if(!id.count(p)) continue;
				int idx=id[p];
				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	9 ms	7424 KB	Output is correct
2	Correct	10 ms	7424 KB	Output is correct
3	Correct	8 ms	7424 KB	Output is correct
4	Correct	9 ms	7424 KB	Output is correct
5	Correct	9 ms	7424 KB	Output is correct
6	Correct	10 ms	7472 KB	Output is correct
7	Correct	9 ms	7424 KB	Output is correct
8	Correct	9 ms	7424 KB	Output is correct
9	Correct	10 ms	7396 KB	Output is correct
10	Correct	10 ms	7424 KB	Output is correct
11	Correct	9 ms	7424 KB	Output is correct
12	Correct	8 ms	7424 KB	Output is correct
13	Correct	9 ms	7424 KB	Output is correct
14	Correct	8 ms	7424 KB	Output is correct
15	Correct	8 ms	7424 KB	Output is correct
16	Correct	10 ms	7424 KB	Output is correct
17	Correct	9 ms	7552 KB	Output is correct
18	Correct	9 ms	7424 KB	Output is correct
19	Correct	15 ms	7936 KB	Output is correct
20	Correct	17 ms	8060 KB	Output is correct
21	Correct	13 ms	7936 KB	Output is correct
22	Correct	27 ms	9084 KB	Output is correct
23	Correct	27 ms	9212 KB	Output is correct
24	Correct	28 ms	9084 KB	Output is correct
25	Correct	31 ms	8960 KB	Output is correct
26	Correct	29 ms	8960 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	366 ms	33600 KB	Output is correct
2	Correct	488 ms	44588 KB	Output is correct
3	Correct	377 ms	39760 KB	Output is correct
4	Correct	339 ms	38104 KB	Output is correct
5	Correct	809 ms	95804 KB	Output is correct
6	Correct	1650 ms	140392 KB	Output is correct
7	Correct	882 ms	105852 KB	Output is correct
8	Correct	1203 ms	130668 KB	Output is correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	7424 KB	Output is correct
2	Correct	789 ms	41644 KB	Output is correct
3	Execution timed out	3032 ms	120820 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

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

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	7424 KB	Output is correct
2	Correct	10 ms	7424 KB	Output is correct
3	Correct	8 ms	7424 KB	Output is correct
4	Correct	9 ms	7424 KB	Output is correct
5	Correct	9 ms	7424 KB	Output is correct
6	Correct	10 ms	7472 KB	Output is correct
7	Correct	9 ms	7424 KB	Output is correct
8	Correct	9 ms	7424 KB	Output is correct
9	Correct	10 ms	7396 KB	Output is correct
10	Correct	10 ms	7424 KB	Output is correct
11	Correct	9 ms	7424 KB	Output is correct
12	Correct	8 ms	7424 KB	Output is correct
13	Correct	9 ms	7424 KB	Output is correct
14	Correct	8 ms	7424 KB	Output is correct
15	Correct	8 ms	7424 KB	Output is correct
16	Correct	10 ms	7424 KB	Output is correct
17	Correct	9 ms	7552 KB	Output is correct
18	Correct	9 ms	7424 KB	Output is correct
19	Correct	15 ms	7936 KB	Output is correct
20	Correct	17 ms	8060 KB	Output is correct
21	Correct	13 ms	7936 KB	Output is correct
22	Correct	27 ms	9084 KB	Output is correct
23	Correct	27 ms	9212 KB	Output is correct
24	Correct	28 ms	9084 KB	Output is correct
25	Correct	31 ms	8960 KB	Output is correct
26	Correct	29 ms	8960 KB	Output is correct
27	Correct	23 ms	8440 KB	Output is correct
28	Correct	20 ms	8568 KB	Output is correct
29	Correct	22 ms	8432 KB	Output is correct
30	Correct	53 ms	10992 KB	Output is correct
31	Correct	50 ms	10832 KB	Output is correct
32	Correct	50 ms	10840 KB	Output is correct
33	Correct	108 ms	17252 KB	Output is correct
34	Correct	117 ms	17308 KB	Output is correct
35	Correct	124 ms	18780 KB	Output is correct
36	Correct	837 ms	45816 KB	Output is correct
37	Correct	840 ms	45532 KB	Output is correct
38	Correct	926 ms	44380 KB	Output is correct
39	Correct	878 ms	41936 KB	Output is correct
40	Correct	754 ms	42620 KB	Output is correct
41	Correct	761 ms	43204 KB	Output is correct
42	Correct	479 ms	40668 KB	Output is correct
43	Correct	1006 ms	48572 KB	Output is correct
44	Correct	797 ms	49764 KB	Output is correct
45	Correct	920 ms	48260 KB	Output is correct
46	Correct	867 ms	47988 KB	Output is correct
47	Correct	813 ms	48188 KB	Output is correct
48	Correct	812 ms	49288 KB	Output is correct
49	Correct	792 ms	48920 KB	Output is correct
50	Correct	949 ms	48052 KB	Output is correct

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	7424 KB	Output is correct
2	Correct	10 ms	7424 KB	Output is correct
3	Correct	8 ms	7424 KB	Output is correct
4	Correct	9 ms	7424 KB	Output is correct
5	Correct	9 ms	7424 KB	Output is correct
6	Correct	10 ms	7472 KB	Output is correct
7	Correct	9 ms	7424 KB	Output is correct
8	Correct	9 ms	7424 KB	Output is correct
9	Correct	10 ms	7396 KB	Output is correct
10	Correct	10 ms	7424 KB	Output is correct
11	Correct	9 ms	7424 KB	Output is correct
12	Correct	8 ms	7424 KB	Output is correct
13	Correct	9 ms	7424 KB	Output is correct
14	Correct	8 ms	7424 KB	Output is correct
15	Correct	8 ms	7424 KB	Output is correct
16	Correct	10 ms	7424 KB	Output is correct
17	Correct	9 ms	7552 KB	Output is correct
18	Correct	9 ms	7424 KB	Output is correct
19	Correct	15 ms	7936 KB	Output is correct
20	Correct	17 ms	8060 KB	Output is correct
21	Correct	13 ms	7936 KB	Output is correct
22	Correct	27 ms	9084 KB	Output is correct
23	Correct	27 ms	9212 KB	Output is correct
24	Correct	28 ms	9084 KB	Output is correct
25	Correct	31 ms	8960 KB	Output is correct
26	Correct	29 ms	8960 KB	Output is correct
27	Correct	366 ms	33600 KB	Output is correct
28	Correct	488 ms	44588 KB	Output is correct
29	Correct	377 ms	39760 KB	Output is correct
30	Correct	339 ms	38104 KB	Output is correct
31	Correct	809 ms	95804 KB	Output is correct
32	Correct	1650 ms	140392 KB	Output is correct
33	Correct	882 ms	105852 KB	Output is correct
34	Correct	1203 ms	130668 KB	Output is correct
35	Correct	8 ms	7424 KB	Output is correct
36	Correct	789 ms	41644 KB	Output is correct
37	Execution timed out	3032 ms	120820 KB	Time limit exceeded
38	Halted	0 ms	0 KB	-

답안 #99823

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