답안 #368178

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
368178	2021-02-19T17:29:39 Z	YJU	원 고르기 (APIO18_circle_selection)	C++14	100 / 100	2308 ms	42240 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;


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)){
		vector<pair<pll,ll> > loc;
		while(R==0);
		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	3 ms	2796 KB	Output is correct
18	Correct	2 ms	2796 KB	Output is correct
19	Correct	5 ms	3372 KB	Output is correct
20	Correct	5 ms	3372 KB	Output is correct
21	Correct	5 ms	3372 KB	Output is correct
22	Correct	8 ms	3372 KB	Output is correct
23	Correct	9 ms	3356 KB	Output is correct
24	Correct	8 ms	3372 KB	Output is correct
25	Correct	10 ms	3372 KB	Output is correct
26	Correct	8 ms	3372 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	204 ms	28700 KB	Output is correct
2	Correct	235 ms	28736 KB	Output is correct
3	Correct	229 ms	28736 KB	Output is correct
4	Correct	224 ms	28736 KB	Output is correct
5	Correct	252 ms	28736 KB	Output is correct
6	Correct	360 ms	28736 KB	Output is correct
7	Correct	265 ms	28992 KB	Output is correct
8	Correct	280 ms	29120 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2668 KB	Output is correct
2	Correct	175 ms	14168 KB	Output is correct
3	Correct	584 ms	36796 KB	Output is correct
4	Correct	576 ms	36928 KB	Output is correct
5	Correct	567 ms	41656 KB	Output is correct
6	Correct	241 ms	22476 KB	Output is correct
7	Correct	120 ms	12120 KB	Output is correct
8	Correct	21 ms	4708 KB	Output is correct
9	Correct	645 ms	42240 KB	Output is correct
10	Correct	584 ms	39592 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	516 ms	28736 KB	Output is correct
2	Correct	427 ms	35776 KB	Output is correct
3	Correct	299 ms	37104 KB	Output is correct
4	Correct	439 ms	36032 KB	Output is correct
5	Correct	436 ms	36416 KB	Output is correct
6	Correct	280 ms	37184 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	3 ms	2796 KB	Output is correct
18	Correct	2 ms	2796 KB	Output is correct
19	Correct	5 ms	3372 KB	Output is correct
20	Correct	5 ms	3372 KB	Output is correct
21	Correct	5 ms	3372 KB	Output is correct
22	Correct	8 ms	3372 KB	Output is correct
23	Correct	9 ms	3356 KB	Output is correct
24	Correct	8 ms	3372 KB	Output is correct
25	Correct	10 ms	3372 KB	Output is correct
26	Correct	8 ms	3372 KB	Output is correct
27	Correct	9 ms	3944 KB	Output is correct
28	Correct	9 ms	3944 KB	Output is correct
29	Correct	9 ms	3944 KB	Output is correct
30	Correct	16 ms	3944 KB	Output is correct
31	Correct	15 ms	3944 KB	Output is correct
32	Correct	16 ms	3944 KB	Output is correct
33	Correct	76 ms	14600 KB	Output is correct
34	Correct	75 ms	14556 KB	Output is correct
35	Correct	84 ms	14428 KB	Output is correct
36	Correct	163 ms	13912 KB	Output is correct
37	Correct	169 ms	14040 KB	Output is correct
38	Correct	170 ms	14168 KB	Output is correct
39	Correct	689 ms	15668 KB	Output is correct
40	Correct	670 ms	15560 KB	Output is correct
41	Correct	684 ms	15720 KB	Output is correct
42	Correct	94 ms	13016 KB	Output is correct
43	Correct	134 ms	14168 KB	Output is correct
44	Correct	139 ms	14040 KB	Output is correct
45	Correct	130 ms	14040 KB	Output is correct
46	Correct	135 ms	14040 KB	Output is correct
47	Correct	133 ms	14040 KB	Output is correct
48	Correct	131 ms	14040 KB	Output is correct
49	Correct	136 ms	14040 KB	Output is correct
50	Correct	136 ms	14040 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	3 ms	2796 KB	Output is correct
18	Correct	2 ms	2796 KB	Output is correct
19	Correct	5 ms	3372 KB	Output is correct
20	Correct	5 ms	3372 KB	Output is correct
21	Correct	5 ms	3372 KB	Output is correct
22	Correct	8 ms	3372 KB	Output is correct
23	Correct	9 ms	3356 KB	Output is correct
24	Correct	8 ms	3372 KB	Output is correct
25	Correct	10 ms	3372 KB	Output is correct
26	Correct	8 ms	3372 KB	Output is correct
27	Correct	204 ms	28700 KB	Output is correct
28	Correct	235 ms	28736 KB	Output is correct
29	Correct	229 ms	28736 KB	Output is correct
30	Correct	224 ms	28736 KB	Output is correct
31	Correct	252 ms	28736 KB	Output is correct
32	Correct	360 ms	28736 KB	Output is correct
33	Correct	265 ms	28992 KB	Output is correct
34	Correct	280 ms	29120 KB	Output is correct
35	Correct	2 ms	2668 KB	Output is correct
36	Correct	175 ms	14168 KB	Output is correct
37	Correct	584 ms	36796 KB	Output is correct
38	Correct	576 ms	36928 KB	Output is correct
39	Correct	567 ms	41656 KB	Output is correct
40	Correct	241 ms	22476 KB	Output is correct
41	Correct	120 ms	12120 KB	Output is correct
42	Correct	21 ms	4708 KB	Output is correct
43	Correct	645 ms	42240 KB	Output is correct
44	Correct	584 ms	39592 KB	Output is correct
45	Correct	516 ms	28736 KB	Output is correct
46	Correct	427 ms	35776 KB	Output is correct
47	Correct	299 ms	37104 KB	Output is correct
48	Correct	439 ms	36032 KB	Output is correct
49	Correct	436 ms	36416 KB	Output is correct
50	Correct	280 ms	37184 KB	Output is correct
51	Correct	9 ms	3944 KB	Output is correct
52	Correct	9 ms	3944 KB	Output is correct
53	Correct	9 ms	3944 KB	Output is correct
54	Correct	16 ms	3944 KB	Output is correct
55	Correct	15 ms	3944 KB	Output is correct
56	Correct	16 ms	3944 KB	Output is correct
57	Correct	76 ms	14600 KB	Output is correct
58	Correct	75 ms	14556 KB	Output is correct
59	Correct	84 ms	14428 KB	Output is correct
60	Correct	163 ms	13912 KB	Output is correct
61	Correct	169 ms	14040 KB	Output is correct
62	Correct	170 ms	14168 KB	Output is correct
63	Correct	689 ms	15668 KB	Output is correct
64	Correct	670 ms	15560 KB	Output is correct
65	Correct	684 ms	15720 KB	Output is correct
66	Correct	94 ms	13016 KB	Output is correct
67	Correct	134 ms	14168 KB	Output is correct
68	Correct	139 ms	14040 KB	Output is correct
69	Correct	130 ms	14040 KB	Output is correct
70	Correct	135 ms	14040 KB	Output is correct
71	Correct	133 ms	14040 KB	Output is correct
72	Correct	131 ms	14040 KB	Output is correct
73	Correct	136 ms	14040 KB	Output is correct
74	Correct	136 ms	14040 KB	Output is correct
75	Correct	249 ms	37952 KB	Output is correct
76	Correct	252 ms	37440 KB	Output is correct
77	Correct	242 ms	37568 KB	Output is correct
78	Correct	227 ms	37696 KB	Output is correct
79	Correct	315 ms	37440 KB	Output is correct
80	Correct	218 ms	37696 KB	Output is correct
81	Correct	574 ms	36800 KB	Output is correct
82	Correct	575 ms	36692 KB	Output is correct
83	Correct	566 ms	36544 KB	Output is correct
84	Correct	580 ms	37064 KB	Output is correct
85	Correct	563 ms	36672 KB	Output is correct
86	Correct	563 ms	36672 KB	Output is correct
87	Correct	633 ms	36672 KB	Output is correct
88	Correct	2213 ms	34972 KB	Output is correct
89	Correct	2308 ms	35092 KB	Output is correct
90	Correct	2308 ms	35184 KB	Output is correct
91	Correct	2196 ms	35044 KB	Output is correct
92	Correct	2304 ms	35232 KB	Output is correct
93	Correct	478 ms	35648 KB	Output is correct
94	Correct	485 ms	36160 KB	Output is correct
95	Correct	472 ms	35516 KB	Output is correct
96	Correct	483 ms	35712 KB	Output is correct
97	Correct	622 ms	35520 KB	Output is correct
98	Correct	394 ms	36032 KB	Output is correct
99	Correct	486 ms	35776 KB	Output is correct
100	Correct	446 ms	35520 KB	Output is correct
101	Correct	472 ms	35900 KB	Output is correct
102	Correct	487 ms	35904 KB	Output is correct
103	Correct	595 ms	35648 KB	Output is correct
104	Correct	489 ms	35388 KB	Output is correct
105	Correct	365 ms	33596 KB	Output is correct
106	Correct	422 ms	36416 KB	Output is correct
107	Correct	438 ms	36544 KB	Output is correct
108	Correct	425 ms	36544 KB	Output is correct
109	Correct	428 ms	36416 KB	Output is correct
110	Correct	428 ms	36544 KB	Output is correct
111	Correct	427 ms	36544 KB	Output is correct
112	Correct	427 ms	36416 KB	Output is correct
113	Correct	428 ms	36544 KB	Output is correct
114	Correct	427 ms	36444 KB	Output is correct
115	Correct	426 ms	36416 KB	Output is correct
116	Correct	419 ms	36416 KB	Output is correct

답안 #368178

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