답안 #75673 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
75673	2018-09-10T17:26:29 Z	tmwilliamlin168	원 고르기 (APIO18_circle_selection)	C++17	100 / 100	2936 ms	157104 KB

circle_selection

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mxN=3e5;
int n, p[mxN], p2[mxN], a[mxN], k=30;
ll x[mxN], y[mxN], r[mxN];
unordered_map<int, vector<int>> mp;

struct cmp1 {
	__attribute__((always_inline)) bool operator()(const int &a, const int &b) {
		return y[a]>>k<b;
	}
};

void rs(int k) {
	mp.clear();
	for(int i=0; i<n; ++i)
		if(a[p2[i]]==-1)
			mp[x[p2[i]]>>k].push_back(p2[i]);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for(int i=0; i<n; ++i) {
		cin >> x[i] >> y[i] >> r[i];
		p[i]=p2[i]=i;
	}
	sort(p, p+n, [&](const int &a, const int &b) {
		return r[a]==r[b]?a<b:r[a]>r[b];
	});
	sort(p2, p2+n, [&](const int &a, const int &b) {
		return y[a]<y[b];
	});
	memset(a, -1, 4*n);
	for(int i=-1; i+1<n; --i, --k) {
		rs(k);
		while(++i<n&&r[p[i]]>=1<<(k-1)) {
			if(a[p[i]]!=-1)
				continue;
			for(ll b=(x[p[i]]>>k)-2; b<=(x[p[i]]>>k)+2; ++b) {
				auto mf=mp.find(b);
				if(mf==mp.end())
					continue;
				vector<int> &v=mf->second;
				for(int j=lower_bound(v.begin(), v.end(), (y[p[i]]>>k)-2, cmp1())-v.begin(); j<v.size()&&y[v[j]]>>k<=(y[p[i]]>>k)+2; ++j) {
					ll dx=x[p[i]]-x[v[j]], dy=y[p[i]]-y[v[j]], rs=r[p[i]]+r[v[j]];
					if(dx*dx+dy*dy<=rs*rs&&a[v[j]]==-1)
						a[v[j]]=p[i];
				}
			}
		}
	}
	for(int i=0; i<n; ++i)
		cout << a[i]+1 << " ";
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:50:83: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=lower_bound(v.begin(), v.end(), (y[p[i]]>>k)-2, cmp1())-v.begin(); j<v.size()&&y[v[j]]>>k<=(y[p[i]]>>k)+2; ++j) {
                                                                                  ~^~~~~~~~~

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	436 KB	Output is correct
3	Correct	2 ms	436 KB	Output is correct
4	Correct	2 ms	436 KB	Output is correct
5	Correct	2 ms	436 KB	Output is correct
6	Correct	2 ms	476 KB	Output is correct
7	Correct	2 ms	476 KB	Output is correct
8	Correct	2 ms	648 KB	Output is correct
9	Correct	2 ms	648 KB	Output is correct
10	Correct	2 ms	648 KB	Output is correct
11	Correct	2 ms	668 KB	Output is correct
12	Correct	3 ms	668 KB	Output is correct
13	Correct	2 ms	668 KB	Output is correct
14	Correct	2 ms	668 KB	Output is correct
15	Correct	2 ms	668 KB	Output is correct
16	Correct	3 ms	668 KB	Output is correct
17	Correct	3 ms	668 KB	Output is correct
18	Correct	3 ms	668 KB	Output is correct
19	Correct	6 ms	872 KB	Output is correct
20	Correct	6 ms	872 KB	Output is correct
21	Correct	6 ms	888 KB	Output is correct
22	Correct	11 ms	1032 KB	Output is correct
23	Correct	10 ms	1032 KB	Output is correct
24	Correct	12 ms	1056 KB	Output is correct
25	Correct	16 ms	1432 KB	Output is correct
26	Correct	12 ms	1432 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	229 ms	13476 KB	Output is correct
2	Correct	245 ms	13792 KB	Output is correct
3	Correct	253 ms	13792 KB	Output is correct
4	Correct	280 ms	13792 KB	Output is correct
5	Correct	392 ms	15960 KB	Output is correct
6	Correct	738 ms	24424 KB	Output is correct
7	Correct	403 ms	24424 KB	Output is correct
8	Correct	492 ms	24424 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	24424 KB	Output is correct
2	Correct	236 ms	24424 KB	Output is correct
3	Correct	856 ms	24424 KB	Output is correct
4	Correct	864 ms	24424 KB	Output is correct
5	Correct	706 ms	24424 KB	Output is correct
6	Correct	322 ms	24424 KB	Output is correct
7	Correct	162 ms	24424 KB	Output is correct
8	Correct	35 ms	24424 KB	Output is correct
9	Correct	938 ms	24424 KB	Output is correct
10	Correct	636 ms	24424 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	860 ms	24424 KB	Output is correct
2	Correct	2368 ms	40236 KB	Output is correct
3	Correct	391 ms	40236 KB	Output is correct
4	Correct	1550 ms	40236 KB	Output is correct
5	Correct	1694 ms	40236 KB	Output is correct
6	Correct	354 ms	40236 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	436 KB	Output is correct
3	Correct	2 ms	436 KB	Output is correct
4	Correct	2 ms	436 KB	Output is correct
5	Correct	2 ms	436 KB	Output is correct
6	Correct	2 ms	476 KB	Output is correct
7	Correct	2 ms	476 KB	Output is correct
8	Correct	2 ms	648 KB	Output is correct
9	Correct	2 ms	648 KB	Output is correct
10	Correct	2 ms	648 KB	Output is correct
11	Correct	2 ms	668 KB	Output is correct
12	Correct	3 ms	668 KB	Output is correct
13	Correct	2 ms	668 KB	Output is correct
14	Correct	2 ms	668 KB	Output is correct
15	Correct	2 ms	668 KB	Output is correct
16	Correct	3 ms	668 KB	Output is correct
17	Correct	3 ms	668 KB	Output is correct
18	Correct	3 ms	668 KB	Output is correct
19	Correct	6 ms	872 KB	Output is correct
20	Correct	6 ms	872 KB	Output is correct
21	Correct	6 ms	888 KB	Output is correct
22	Correct	11 ms	1032 KB	Output is correct
23	Correct	10 ms	1032 KB	Output is correct
24	Correct	12 ms	1056 KB	Output is correct
25	Correct	16 ms	1432 KB	Output is correct
26	Correct	12 ms	1432 KB	Output is correct
27	Correct	10 ms	40236 KB	Output is correct
28	Correct	10 ms	40236 KB	Output is correct
29	Correct	10 ms	40236 KB	Output is correct
30	Correct	24 ms	40236 KB	Output is correct
31	Correct	22 ms	40236 KB	Output is correct
32	Correct	23 ms	40236 KB	Output is correct
33	Correct	88 ms	40236 KB	Output is correct
34	Correct	91 ms	40236 KB	Output is correct
35	Correct	98 ms	40236 KB	Output is correct
36	Correct	250 ms	40236 KB	Output is correct
37	Correct	238 ms	40236 KB	Output is correct
38	Correct	231 ms	40236 KB	Output is correct
39	Correct	290 ms	40236 KB	Output is correct
40	Correct	321 ms	40236 KB	Output is correct
41	Correct	307 ms	40236 KB	Output is correct
42	Correct	190 ms	40236 KB	Output is correct
43	Correct	299 ms	40236 KB	Output is correct
44	Correct	332 ms	40236 KB	Output is correct
45	Correct	310 ms	40236 KB	Output is correct
46	Correct	309 ms	40236 KB	Output is correct
47	Correct	284 ms	40236 KB	Output is correct
48	Correct	328 ms	40236 KB	Output is correct
49	Correct	317 ms	40236 KB	Output is correct
50	Correct	319 ms	40236 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	436 KB	Output is correct
3	Correct	2 ms	436 KB	Output is correct
4	Correct	2 ms	436 KB	Output is correct
5	Correct	2 ms	436 KB	Output is correct
6	Correct	2 ms	476 KB	Output is correct
7	Correct	2 ms	476 KB	Output is correct
8	Correct	2 ms	648 KB	Output is correct
9	Correct	2 ms	648 KB	Output is correct
10	Correct	2 ms	648 KB	Output is correct
11	Correct	2 ms	668 KB	Output is correct
12	Correct	3 ms	668 KB	Output is correct
13	Correct	2 ms	668 KB	Output is correct
14	Correct	2 ms	668 KB	Output is correct
15	Correct	2 ms	668 KB	Output is correct
16	Correct	3 ms	668 KB	Output is correct
17	Correct	3 ms	668 KB	Output is correct
18	Correct	3 ms	668 KB	Output is correct
19	Correct	6 ms	872 KB	Output is correct
20	Correct	6 ms	872 KB	Output is correct
21	Correct	6 ms	888 KB	Output is correct
22	Correct	11 ms	1032 KB	Output is correct
23	Correct	10 ms	1032 KB	Output is correct
24	Correct	12 ms	1056 KB	Output is correct
25	Correct	16 ms	1432 KB	Output is correct
26	Correct	12 ms	1432 KB	Output is correct
27	Correct	229 ms	13476 KB	Output is correct
28	Correct	245 ms	13792 KB	Output is correct
29	Correct	253 ms	13792 KB	Output is correct
30	Correct	280 ms	13792 KB	Output is correct
31	Correct	392 ms	15960 KB	Output is correct
32	Correct	738 ms	24424 KB	Output is correct
33	Correct	403 ms	24424 KB	Output is correct
34	Correct	492 ms	24424 KB	Output is correct
35	Correct	2 ms	24424 KB	Output is correct
36	Correct	236 ms	24424 KB	Output is correct
37	Correct	856 ms	24424 KB	Output is correct
38	Correct	864 ms	24424 KB	Output is correct
39	Correct	706 ms	24424 KB	Output is correct
40	Correct	322 ms	24424 KB	Output is correct
41	Correct	162 ms	24424 KB	Output is correct
42	Correct	35 ms	24424 KB	Output is correct
43	Correct	938 ms	24424 KB	Output is correct
44	Correct	636 ms	24424 KB	Output is correct
45	Correct	860 ms	24424 KB	Output is correct
46	Correct	2368 ms	40236 KB	Output is correct
47	Correct	391 ms	40236 KB	Output is correct
48	Correct	1550 ms	40236 KB	Output is correct
49	Correct	1694 ms	40236 KB	Output is correct
50	Correct	354 ms	40236 KB	Output is correct
51	Correct	10 ms	40236 KB	Output is correct
52	Correct	10 ms	40236 KB	Output is correct
53	Correct	10 ms	40236 KB	Output is correct
54	Correct	24 ms	40236 KB	Output is correct
55	Correct	22 ms	40236 KB	Output is correct
56	Correct	23 ms	40236 KB	Output is correct
57	Correct	88 ms	40236 KB	Output is correct
58	Correct	91 ms	40236 KB	Output is correct
59	Correct	98 ms	40236 KB	Output is correct
60	Correct	250 ms	40236 KB	Output is correct
61	Correct	238 ms	40236 KB	Output is correct
62	Correct	231 ms	40236 KB	Output is correct
63	Correct	290 ms	40236 KB	Output is correct
64	Correct	321 ms	40236 KB	Output is correct
65	Correct	307 ms	40236 KB	Output is correct
66	Correct	190 ms	40236 KB	Output is correct
67	Correct	299 ms	40236 KB	Output is correct
68	Correct	332 ms	40236 KB	Output is correct
69	Correct	310 ms	40236 KB	Output is correct
70	Correct	309 ms	40236 KB	Output is correct
71	Correct	284 ms	40236 KB	Output is correct
72	Correct	328 ms	40236 KB	Output is correct
73	Correct	317 ms	40236 KB	Output is correct
74	Correct	319 ms	40236 KB	Output is correct
75	Correct	369 ms	40236 KB	Output is correct
76	Correct	378 ms	40236 KB	Output is correct
77	Correct	324 ms	40236 KB	Output is correct
78	Correct	302 ms	40236 KB	Output is correct
79	Correct	357 ms	40236 KB	Output is correct
80	Correct	301 ms	40236 KB	Output is correct
81	Correct	912 ms	40236 KB	Output is correct
82	Correct	959 ms	40236 KB	Output is correct
83	Correct	944 ms	40236 KB	Output is correct
84	Correct	782 ms	40236 KB	Output is correct
85	Correct	858 ms	40236 KB	Output is correct
86	Correct	1014 ms	40236 KB	Output is correct
87	Correct	821 ms	40236 KB	Output is correct
88	Correct	1053 ms	40236 KB	Output is correct
89	Correct	1199 ms	40236 KB	Output is correct
90	Correct	1081 ms	40236 KB	Output is correct
91	Correct	1078 ms	40236 KB	Output is correct
92	Correct	1087 ms	40236 KB	Output is correct
93	Correct	2056 ms	40236 KB	Output is correct
94	Correct	745 ms	40236 KB	Output is correct
95	Correct	2222 ms	40236 KB	Output is correct
96	Correct	2143 ms	40236 KB	Output is correct
97	Correct	961 ms	40236 KB	Output is correct
98	Correct	854 ms	40236 KB	Output is correct
99	Correct	2253 ms	40236 KB	Output is correct
100	Correct	2936 ms	40240 KB	Output is correct
101	Correct	821 ms	40240 KB	Output is correct
102	Correct	1796 ms	53304 KB	Output is correct
103	Correct	913 ms	53304 KB	Output is correct
104	Correct	2370 ms	68280 KB	Output is correct
105	Correct	604 ms	68280 KB	Output is correct
106	Correct	882 ms	75708 KB	Output is correct
107	Correct	935 ms	83676 KB	Output is correct
108	Correct	876 ms	91420 KB	Output is correct
109	Correct	864 ms	99200 KB	Output is correct
110	Correct	872 ms	106860 KB	Output is correct
111	Correct	852 ms	114912 KB	Output is correct
112	Correct	975 ms	122392 KB	Output is correct
113	Correct	917 ms	130108 KB	Output is correct
114	Correct	955 ms	137892 KB	Output is correct
115	Correct	954 ms	145948 KB	Output is correct
116	Correct	1061 ms	157104 KB	Output is correct

답안 #75673

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