oj.uz

Submission #404789

# Submission time Handle Problem Language Result Execution time Memory
404789 2021-05-15T02:32:45 Z jjang36524 Circle selection (APIO18_circle_selection) C++14
49 / 100
 3000 ms 42856 KB 
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
#define int long long
using namespace std;
unordered_map<int, vector<int>>x;
pair<int, int>po[300100];
vector<pair<int, int>>so;
int pre[300100];
int num[300100];
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N;
	cin >> N;
	int i;
	for (i = 0; i < N; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		a += 1LL << 30;
		b += 1LL << 30;
		pre[i] = c;
		so.push_back({ -c,i });
		po[i]={ a,b };
	}
	sort(so.begin(), so.end());
	int gr = 30;
	for (i = 0; i < N; i++)
	{
		x[po[i].first / (1LL << gr)*(1LL<<31)+ po[i].second / (1LL << gr)].push_back(i);
	}
	for (i = 0; i < N; i++)
	{
		if (num[so[i].second])
			continue;
		while ((1LL << gr) >= -so[i].first*2)
		{
			gr--;
			x.clear();
			int i;
			for (i = 0; i < N; i++)
			{
				x[po[i].first / (1LL << gr) * (1LL << 31) + po[i].second / (1LL << gr)].push_back(i);
			}
		}
		int xx = po[so[i].second].first / (1LL << gr);
		int y = po[so[i].second].second / (1LL << gr);
		int j, k;
		for (j = xx - 2; j <= xx + 2; j++)
		{
			for (k = y - 2; k <= y + 2; k++)
			{
				if (!x.count(j * (1LL << 31) + k))
					continue;
				int l;
				for (l = 0; l < x[j*(1LL<<31)+ k].size(); l++)
				{
					int le = x[j * (1LL << 31)+ k][l];
					if (num[le])
						continue;
					if ((po[so[i].second].first - po[le].first) * (po[so[i].second].first - po[le].first) + (po[so[i].second].second - po[le].second) * (po[so[i].second].second - po[le].second) <= (-so[i].first + pre[le]) * (-so[i].first + pre[le]))
					{
						num[le] = so[i].second+1;
					}
				}
			}
		}
	}
	for (i = 0; i < N; i++)
	{
		cout << num[i] << ' ';
	}
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:59:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (l = 0; l < x[j*(1LL<<31)+ k].size(); l++)
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 4 ms 716 KB Output is correct
20 Correct 4 ms 716 KB Output is correct
21 Correct 7 ms 792 KB Output is correct
22 Correct 26 ms 972 KB Output is correct
23 Correct 27 ms 1044 KB Output is correct
24 Correct 26 ms 1044 KB Output is correct
25 Correct 31 ms 1092 KB Output is correct
26 Correct 26 ms 996 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 21388 KB Output is correct
2 Correct 236 ms 21196 KB Output is correct
3 Correct 217 ms 20564 KB Output is correct
4 Correct 215 ms 20260 KB Output is correct
5 Correct 1054 ms 35376 KB Output is correct
6 Correct 2222 ms 42556 KB Output is correct
7 Correct 1505 ms 41460 KB Output is correct
8 Correct 1682 ms 42056 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1058 ms 15032 KB Output is correct
3 Execution timed out 3070 ms 40928 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2659 ms 42856 KB Output is correct
2 Execution timed out 3084 ms 38416 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 4 ms 716 KB Output is correct
20 Correct 4 ms 716 KB Output is correct
21 Correct 7 ms 792 KB Output is correct
22 Correct 26 ms 972 KB Output is correct
23 Correct 27 ms 1044 KB Output is correct
24 Correct 26 ms 1044 KB Output is correct
25 Correct 31 ms 1092 KB Output is correct
26 Correct 26 ms 996 KB Output is correct
27 Correct 18 ms 1696 KB Output is correct
28 Correct 8 ms 1072 KB Output is correct
29 Correct 7 ms 1028 KB Output is correct
30 Correct 57 ms 1608 KB Output is correct
31 Correct 57 ms 1640 KB Output is correct
32 Correct 59 ms 1712 KB Output is correct
33 Correct 68 ms 7448 KB Output is correct
34 Correct 66 ms 7340 KB Output is correct
35 Correct 380 ms 14860 KB Output is correct
36 Correct 975 ms 14828 KB Output is correct
37 Correct 1000 ms 14876 KB Output is correct
38 Correct 981 ms 14820 KB Output is correct
39 Correct 611 ms 14396 KB Output is correct
40 Correct 614 ms 14384 KB Output is correct
41 Correct 598 ms 14388 KB Output is correct
42 Correct 285 ms 11048 KB Output is correct
43 Correct 460 ms 14732 KB Output is correct
44 Correct 437 ms 14588 KB Output is correct
45 Correct 456 ms 14700 KB Output is correct
46 Correct 442 ms 14580 KB Output is correct
47 Correct 458 ms 14596 KB Output is correct
48 Correct 459 ms 14576 KB Output is correct
49 Correct 488 ms 14532 KB Output is correct
50 Correct 481 ms 14580 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 4 ms 716 KB Output is correct
20 Correct 4 ms 716 KB Output is correct
21 Correct 7 ms 792 KB Output is correct
22 Correct 26 ms 972 KB Output is correct
23 Correct 27 ms 1044 KB Output is correct
24 Correct 26 ms 1044 KB Output is correct
25 Correct 31 ms 1092 KB Output is correct
26 Correct 26 ms 996 KB Output is correct
27 Correct 220 ms 21388 KB Output is correct
28 Correct 236 ms 21196 KB Output is correct
29 Correct 217 ms 20564 KB Output is correct
30 Correct 215 ms 20260 KB Output is correct
31 Correct 1054 ms 35376 KB Output is correct
32 Correct 2222 ms 42556 KB Output is correct
33 Correct 1505 ms 41460 KB Output is correct
34 Correct 1682 ms 42056 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 1058 ms 15032 KB Output is correct
37 Execution timed out 3070 ms 40928 KB Time limit exceeded
38 Halted 0 ms 0 KB -