oj.uz

Submission #75644

# Submission time Handle Problem Language Result Execution time Memory
75644 2018-09-10T16:21:07 Z tmwilliamlin168 Circle selection (APIO18_circle_selection) C++14
19 / 100
 3000 ms 154688 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

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

void rs(int k) {
	mp.clear();
	for(int i=0; i<n; ++i)
		if(a[i]==-1)
			mp[x[i]>>k<<32|y[i]>>k].push_back(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]=i;
	}
	sort(p, p+n, [&](const int &a, const int &b) {
		return r[a]==r[b]?a<b:r[a]>r[b];
	});
	memset(a, -1, 4*n);
	for(int i=-1, k=30; i+1<n; --i, --k) {
		rs(k);
		while(++i<n&&r[p[i]]>=1<<(k-1)) {
//			cout << p[i] << endl;
			if(a[p[i]]!=-1)
				continue;
//			cout << p[i] << endl;
			for(ll b=(x[p[i]]>>k)-2; b<=(x[p[i]]>>k)+2; ++b) {
				for(ll c=(y[p[i]]>>k)-2; c<=(y[p[i]]>>k)+2; ++c) {
					int ns=0;
					//vector &v;
					for(int j=0; j<mp[b<<32|c].size(); ++j) {
						ll dx=x[p[i]]-x[mp[b<<32|c][j]], dy=y[p[i]]-y[mp[b<<32|c][j]], rs=r[p[i]]+r[mp[b<<32|c][j]];
						if(dx*dx+dy*dy<=rs*rs)
							a[mp[b<<32|c][j]]=p[i];
						else
							mp[b<<32|c][ns++]=mp[b<<32|c][j];
					}
					mp[b<<32|c].resize(ns);
				}
			}
		}
	}
	for(int i=0; i<n; ++i)
		cout << a[i]+1 << " ";
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int j=0; j<mp[b<<32|c].size(); ++j) {
                   ~^~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 528 KB Output is correct
7 Correct 2 ms 576 KB Output is correct
8 Correct 2 ms 580 KB Output is correct
9 Correct 2 ms 628 KB Output is correct
10 Correct 2 ms 692 KB Output is correct
11 Correct 3 ms 768 KB Output is correct
12 Correct 3 ms 912 KB Output is correct
13 Correct 3 ms 912 KB Output is correct
14 Correct 3 ms 980 KB Output is correct
15 Correct 3 ms 980 KB Output is correct
16 Correct 3 ms 980 KB Output is correct
17 Correct 3 ms 980 KB Output is correct
18 Correct 3 ms 980 KB Output is correct
19 Correct 7 ms 1276 KB Output is correct
20 Correct 7 ms 1520 KB Output is correct
21 Correct 7 ms 1628 KB Output is correct
22 Correct 48 ms 5672 KB Output is correct
23 Correct 25 ms 5672 KB Output is correct
24 Correct 22 ms 5672 KB Output is correct
25 Correct 37 ms 5672 KB Output is correct
26 Correct 34 ms 5672 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 22376 KB Output is correct
2 Correct 329 ms 27460 KB Output is correct
3 Correct 315 ms 35312 KB Output is correct
4 Correct 269 ms 40532 KB Output is correct
5 Correct 516 ms 47840 KB Output is correct
6 Correct 1411 ms 74300 KB Output is correct
7 Correct 613 ms 74300 KB Output is correct
8 Correct 781 ms 74300 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 74300 KB Output is correct
2 Correct 2363 ms 87532 KB Output is correct
3 Execution timed out 3010 ms 117696 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3049 ms 117696 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 528 KB Output is correct
7 Correct 2 ms 576 KB Output is correct
8 Correct 2 ms 580 KB Output is correct
9 Correct 2 ms 628 KB Output is correct
10 Correct 2 ms 692 KB Output is correct
11 Correct 3 ms 768 KB Output is correct
12 Correct 3 ms 912 KB Output is correct
13 Correct 3 ms 912 KB Output is correct
14 Correct 3 ms 980 KB Output is correct
15 Correct 3 ms 980 KB Output is correct
16 Correct 3 ms 980 KB Output is correct
17 Correct 3 ms 980 KB Output is correct
18 Correct 3 ms 980 KB Output is correct
19 Correct 7 ms 1276 KB Output is correct
20 Correct 7 ms 1520 KB Output is correct
21 Correct 7 ms 1628 KB Output is correct
22 Correct 48 ms 5672 KB Output is correct
23 Correct 25 ms 5672 KB Output is correct
24 Correct 22 ms 5672 KB Output is correct
25 Correct 37 ms 5672 KB Output is correct
26 Correct 34 ms 5672 KB Output is correct
27 Correct 15 ms 117696 KB Output is correct
28 Correct 11 ms 117696 KB Output is correct
29 Correct 13 ms 117696 KB Output is correct
30 Correct 50 ms 117696 KB Output is correct
31 Correct 88 ms 117696 KB Output is correct
32 Correct 43 ms 117696 KB Output is correct
33 Correct 91 ms 117696 KB Output is correct
34 Correct 89 ms 117696 KB Output is correct
35 Correct 107 ms 117696 KB Output is correct
36 Correct 1476 ms 154688 KB Output is correct
37 Correct 670 ms 154688 KB Output is correct
38 Correct 1206 ms 154688 KB Output is correct
39 Execution timed out 3036 ms 154688 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 528 KB Output is correct
7 Correct 2 ms 576 KB Output is correct
8 Correct 2 ms 580 KB Output is correct
9 Correct 2 ms 628 KB Output is correct
10 Correct 2 ms 692 KB Output is correct
11 Correct 3 ms 768 KB Output is correct
12 Correct 3 ms 912 KB Output is correct
13 Correct 3 ms 912 KB Output is correct
14 Correct 3 ms 980 KB Output is correct
15 Correct 3 ms 980 KB Output is correct
16 Correct 3 ms 980 KB Output is correct
17 Correct 3 ms 980 KB Output is correct
18 Correct 3 ms 980 KB Output is correct
19 Correct 7 ms 1276 KB Output is correct
20 Correct 7 ms 1520 KB Output is correct
21 Correct 7 ms 1628 KB Output is correct
22 Correct 48 ms 5672 KB Output is correct
23 Correct 25 ms 5672 KB Output is correct
24 Correct 22 ms 5672 KB Output is correct
25 Correct 37 ms 5672 KB Output is correct
26 Correct 34 ms 5672 KB Output is correct
27 Correct 305 ms 22376 KB Output is correct
28 Correct 329 ms 27460 KB Output is correct
29 Correct 315 ms 35312 KB Output is correct
30 Correct 269 ms 40532 KB Output is correct
31 Correct 516 ms 47840 KB Output is correct
32 Correct 1411 ms 74300 KB Output is correct
33 Correct 613 ms 74300 KB Output is correct
34 Correct 781 ms 74300 KB Output is correct
35 Correct 3 ms 74300 KB Output is correct
36 Correct 2363 ms 87532 KB Output is correct
37 Execution timed out 3010 ms 117696 KB Time limit exceeded
38 Halted 0 ms 0 KB -