답안 #368179

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
368179	2021-02-19T17:31:28 Z	YJU	원 고르기 (APIO18_circle_selection)	C++14	100 / 100	2079 ms	30732 KB

circle_selection

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=3e5+5;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

struct circle{
	ll r,x,y,id;
	bool operator <(circle B){
		return (r!=B.r?r>B.r:id<B.id);
	}
};

bool inter(circle A,circle B){
	return (SQ(A.r+B.r)>=SQ(A.x-B.x)+SQ(A.y-B.y));
}

ll n,ans[N];
vector<circle> cir;
vector<pair<pll,ll> > loc;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	memset(ans,-1,sizeof(ans));
	cin>>n;
	cir.resize(n);
	REP(i,n)cin>>cir[i].x>>cir[i].y>>cir[i].r,cir[i].id=i;
	sort(cir.begin(),cir.end());
	ll R=cir[0].r+1;
	while(SZ(cir)){
		loc.clear();
		REP(i,SZ(cir))loc.pb(mp(mp(cir[i].x/R,cir[i].y/R),i));
		sort(loc.begin(),loc.end());
		for(auto i:cir){
			if(ans[i.id]!=-1)continue;
			if(i.r<R/2)break;
			ans[i.id]=i.id;
			ll cx=i.x/R,cy=i.y/R;
			for(int x=cx-2;x<=cx+2;x++){
				pair<pll,ll> pos=mp(mp(x,cy-2),-1);
				for(int j=lwb(loc.begin(),loc.end(),pos)-loc.begin();j<SZ(loc);j++){
					if(loc[j].X.X!=x||loc[j].X.Y>cy+2)break;
					if(ans[cir[loc[j].Y].id]==-1&&inter(i,cir[loc[j].Y])){
						ans[cir[loc[j].Y].id]=i.id;
					}
				}
			}
		}
		vector<circle> tmp=cir;
		cir.clear();
		for(auto i:tmp){
			if(ans[i.id]==-1)cir.pb(i);
		}
		R>>=1;
	}
	REP(i,n)cout<<ans[i]+1<<(i==n-1?"\n":" ");
	return 0;
}
/*
11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1
*/

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2668 KB	Output is correct
2	Correct	2 ms	2668 KB	Output is correct
3	Correct	2 ms	2668 KB	Output is correct
4	Correct	2 ms	2668 KB	Output is correct
5	Correct	2 ms	2668 KB	Output is correct
6	Correct	2 ms	2668 KB	Output is correct
7	Correct	2 ms	2668 KB	Output is correct
8	Correct	2 ms	2668 KB	Output is correct
9	Correct	2 ms	2668 KB	Output is correct
10	Correct	2 ms	2668 KB	Output is correct
11	Correct	2 ms	2668 KB	Output is correct
12	Correct	2 ms	2668 KB	Output is correct
13	Correct	2 ms	2668 KB	Output is correct
14	Correct	2 ms	2668 KB	Output is correct
15	Correct	2 ms	2668 KB	Output is correct
16	Correct	2 ms	2796 KB	Output is correct
17	Correct	2 ms	2796 KB	Output is correct
18	Correct	2 ms	2796 KB	Output is correct
19	Correct	5 ms	3244 KB	Output is correct
20	Correct	5 ms	3244 KB	Output is correct
21	Correct	5 ms	3244 KB	Output is correct
22	Correct	8 ms	3244 KB	Output is correct
23	Correct	9 ms	3244 KB	Output is correct
24	Correct	8 ms	3244 KB	Output is correct
25	Correct	8 ms	3244 KB	Output is correct
26	Correct	8 ms	3244 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	208 ms	28608 KB	Output is correct
2	Correct	222 ms	28608 KB	Output is correct
3	Correct	223 ms	28608 KB	Output is correct
4	Correct	228 ms	28608 KB	Output is correct
5	Correct	248 ms	28608 KB	Output is correct
6	Correct	342 ms	28608 KB	Output is correct
7	Correct	256 ms	28736 KB	Output is correct
8	Correct	271 ms	28608 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2668 KB	Output is correct
2	Correct	166 ms	11480 KB	Output is correct
3	Correct	572 ms	28864 KB	Output is correct
4	Correct	563 ms	28864 KB	Output is correct
5	Correct	545 ms	28424 KB	Output is correct
6	Correct	244 ms	16464 KB	Output is correct
7	Correct	109 ms	10072 KB	Output is correct
8	Correct	20 ms	4452 KB	Output is correct
9	Correct	588 ms	29196 KB	Output is correct
10	Correct	524 ms	30436 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	490 ms	28608 KB	Output is correct
2	Correct	432 ms	28864 KB	Output is correct
3	Correct	298 ms	28736 KB	Output is correct
4	Correct	445 ms	28864 KB	Output is correct
5	Correct	422 ms	28736 KB	Output is correct
6	Correct	281 ms	28736 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2668 KB	Output is correct
2	Correct	2 ms	2668 KB	Output is correct
3	Correct	2 ms	2668 KB	Output is correct
4	Correct	2 ms	2668 KB	Output is correct
5	Correct	2 ms	2668 KB	Output is correct
6	Correct	2 ms	2668 KB	Output is correct
7	Correct	2 ms	2668 KB	Output is correct
8	Correct	2 ms	2668 KB	Output is correct
9	Correct	2 ms	2668 KB	Output is correct
10	Correct	2 ms	2668 KB	Output is correct
11	Correct	2 ms	2668 KB	Output is correct
12	Correct	2 ms	2668 KB	Output is correct
13	Correct	2 ms	2668 KB	Output is correct
14	Correct	2 ms	2668 KB	Output is correct
15	Correct	2 ms	2668 KB	Output is correct
16	Correct	2 ms	2796 KB	Output is correct
17	Correct	2 ms	2796 KB	Output is correct
18	Correct	2 ms	2796 KB	Output is correct
19	Correct	5 ms	3244 KB	Output is correct
20	Correct	5 ms	3244 KB	Output is correct
21	Correct	5 ms	3244 KB	Output is correct
22	Correct	8 ms	3244 KB	Output is correct
23	Correct	9 ms	3244 KB	Output is correct
24	Correct	8 ms	3244 KB	Output is correct
25	Correct	8 ms	3244 KB	Output is correct
26	Correct	8 ms	3244 KB	Output is correct
27	Correct	9 ms	3688 KB	Output is correct
28	Correct	8 ms	3688 KB	Output is correct
29	Correct	9 ms	3688 KB	Output is correct
30	Correct	15 ms	3688 KB	Output is correct
31	Correct	15 ms	3688 KB	Output is correct
32	Correct	15 ms	3688 KB	Output is correct
33	Correct	82 ms	11484 KB	Output is correct
34	Correct	72 ms	11484 KB	Output is correct
35	Correct	81 ms	11484 KB	Output is correct
36	Correct	155 ms	11480 KB	Output is correct
37	Correct	161 ms	11736 KB	Output is correct
38	Correct	166 ms	11736 KB	Output is correct
39	Correct	569 ms	12056 KB	Output is correct
40	Correct	573 ms	12056 KB	Output is correct
41	Correct	561 ms	12184 KB	Output is correct
42	Correct	102 ms	11608 KB	Output is correct
43	Correct	128 ms	11608 KB	Output is correct
44	Correct	130 ms	11608 KB	Output is correct
45	Correct	131 ms	11608 KB	Output is correct
46	Correct	127 ms	11608 KB	Output is correct
47	Correct	137 ms	11608 KB	Output is correct
48	Correct	144 ms	11556 KB	Output is correct
49	Correct	129 ms	11616 KB	Output is correct
50	Correct	130 ms	11608 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2668 KB	Output is correct
2	Correct	2 ms	2668 KB	Output is correct
3	Correct	2 ms	2668 KB	Output is correct
4	Correct	2 ms	2668 KB	Output is correct
5	Correct	2 ms	2668 KB	Output is correct
6	Correct	2 ms	2668 KB	Output is correct
7	Correct	2 ms	2668 KB	Output is correct
8	Correct	2 ms	2668 KB	Output is correct
9	Correct	2 ms	2668 KB	Output is correct
10	Correct	2 ms	2668 KB	Output is correct
11	Correct	2 ms	2668 KB	Output is correct
12	Correct	2 ms	2668 KB	Output is correct
13	Correct	2 ms	2668 KB	Output is correct
14	Correct	2 ms	2668 KB	Output is correct
15	Correct	2 ms	2668 KB	Output is correct
16	Correct	2 ms	2796 KB	Output is correct
17	Correct	2 ms	2796 KB	Output is correct
18	Correct	2 ms	2796 KB	Output is correct
19	Correct	5 ms	3244 KB	Output is correct
20	Correct	5 ms	3244 KB	Output is correct
21	Correct	5 ms	3244 KB	Output is correct
22	Correct	8 ms	3244 KB	Output is correct
23	Correct	9 ms	3244 KB	Output is correct
24	Correct	8 ms	3244 KB	Output is correct
25	Correct	8 ms	3244 KB	Output is correct
26	Correct	8 ms	3244 KB	Output is correct
27	Correct	208 ms	28608 KB	Output is correct
28	Correct	222 ms	28608 KB	Output is correct
29	Correct	223 ms	28608 KB	Output is correct
30	Correct	228 ms	28608 KB	Output is correct
31	Correct	248 ms	28608 KB	Output is correct
32	Correct	342 ms	28608 KB	Output is correct
33	Correct	256 ms	28736 KB	Output is correct
34	Correct	271 ms	28608 KB	Output is correct
35	Correct	2 ms	2668 KB	Output is correct
36	Correct	166 ms	11480 KB	Output is correct
37	Correct	572 ms	28864 KB	Output is correct
38	Correct	563 ms	28864 KB	Output is correct
39	Correct	545 ms	28424 KB	Output is correct
40	Correct	244 ms	16464 KB	Output is correct
41	Correct	109 ms	10072 KB	Output is correct
42	Correct	20 ms	4452 KB	Output is correct
43	Correct	588 ms	29196 KB	Output is correct
44	Correct	524 ms	30436 KB	Output is correct
45	Correct	490 ms	28608 KB	Output is correct
46	Correct	432 ms	28864 KB	Output is correct
47	Correct	298 ms	28736 KB	Output is correct
48	Correct	445 ms	28864 KB	Output is correct
49	Correct	422 ms	28736 KB	Output is correct
50	Correct	281 ms	28736 KB	Output is correct
51	Correct	9 ms	3688 KB	Output is correct
52	Correct	8 ms	3688 KB	Output is correct
53	Correct	9 ms	3688 KB	Output is correct
54	Correct	15 ms	3688 KB	Output is correct
55	Correct	15 ms	3688 KB	Output is correct
56	Correct	15 ms	3688 KB	Output is correct
57	Correct	82 ms	11484 KB	Output is correct
58	Correct	72 ms	11484 KB	Output is correct
59	Correct	81 ms	11484 KB	Output is correct
60	Correct	155 ms	11480 KB	Output is correct
61	Correct	161 ms	11736 KB	Output is correct
62	Correct	166 ms	11736 KB	Output is correct
63	Correct	569 ms	12056 KB	Output is correct
64	Correct	573 ms	12056 KB	Output is correct
65	Correct	561 ms	12184 KB	Output is correct
66	Correct	102 ms	11608 KB	Output is correct
67	Correct	128 ms	11608 KB	Output is correct
68	Correct	130 ms	11608 KB	Output is correct
69	Correct	131 ms	11608 KB	Output is correct
70	Correct	127 ms	11608 KB	Output is correct
71	Correct	137 ms	11608 KB	Output is correct
72	Correct	144 ms	11556 KB	Output is correct
73	Correct	129 ms	11616 KB	Output is correct
74	Correct	130 ms	11608 KB	Output is correct
75	Correct	247 ms	28736 KB	Output is correct
76	Correct	248 ms	29032 KB	Output is correct
77	Correct	237 ms	28736 KB	Output is correct
78	Correct	223 ms	28736 KB	Output is correct
79	Correct	308 ms	28736 KB	Output is correct
80	Correct	215 ms	28736 KB	Output is correct
81	Correct	554 ms	28736 KB	Output is correct
82	Correct	549 ms	28788 KB	Output is correct
83	Correct	542 ms	28864 KB	Output is correct
84	Correct	590 ms	28816 KB	Output is correct
85	Correct	591 ms	28736 KB	Output is correct
86	Correct	607 ms	28736 KB	Output is correct
87	Correct	627 ms	28736 KB	Output is correct
88	Correct	1990 ms	30472 KB	Output is correct
89	Correct	2079 ms	30604 KB	Output is correct
90	Correct	2027 ms	30628 KB	Output is correct
91	Correct	1926 ms	30732 KB	Output is correct
92	Correct	2008 ms	30712 KB	Output is correct
93	Correct	464 ms	28868 KB	Output is correct
94	Correct	492 ms	28864 KB	Output is correct
95	Correct	481 ms	28864 KB	Output is correct
96	Correct	469 ms	28992 KB	Output is correct
97	Correct	604 ms	28864 KB	Output is correct
98	Correct	399 ms	28992 KB	Output is correct
99	Correct	479 ms	28864 KB	Output is correct
100	Correct	440 ms	28864 KB	Output is correct
101	Correct	471 ms	28864 KB	Output is correct
102	Correct	477 ms	28736 KB	Output is correct
103	Correct	586 ms	28736 KB	Output is correct
104	Correct	481 ms	28736 KB	Output is correct
105	Correct	364 ms	28864 KB	Output is correct
106	Correct	471 ms	28736 KB	Output is correct
107	Correct	415 ms	28736 KB	Output is correct
108	Correct	429 ms	28864 KB	Output is correct
109	Correct	431 ms	28864 KB	Output is correct
110	Correct	431 ms	28736 KB	Output is correct
111	Correct	420 ms	28864 KB	Output is correct
112	Correct	431 ms	28788 KB	Output is correct
113	Correct	419 ms	28864 KB	Output is correct
114	Correct	432 ms	28864 KB	Output is correct
115	Correct	427 ms	28736 KB	Output is correct
116	Correct	437 ms	28736 KB	Output is correct

답안 #368179

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 12.0 / 12.0

Subtask #3 15.0 / 15.0

Subtask #4 23.0 / 23.0

Subtask #5 30.0 / 30.0

Subtask #6 13.0 / 13.0

Subtask #1
7.0 / 7.0

Subtask #2
12.0 / 12.0

Subtask #3
15.0 / 15.0

Subtask #4
23.0 / 23.0

Subtask #5
30.0 / 30.0

Subtask #6
13.0 / 13.0