oj.uz

Submission #404800

# Submission time Handle Problem Language Result Execution time Memory
404800 2021-05-15T02:50:44 Z jjang36524 Circle selection (APIO18_circle_selection) C++14
64 / 100
 3000 ms 43088 KB 
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
#define int long long
using namespace std;
unordered_map<int, vector<int>>x;
int po[300100][2];
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][0] = a;
		po[i][1] = b;
	}
	sort(so.begin(), so.end());
	int gr = 30;
	for (i = 0; i < N; i++)
	{
		x[po[i][0] / (1LL << gr) * (1LL << 31) + po[i][1] / (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++)
			{
				if (num[i])
					continue;
				x[po[i][0] / (1LL << gr) * (1LL << 31) + po[i][1] / (1LL << gr)].push_back(i);
			}
		}
		int cuuu = so[i].second;
		int xx = po[cuuu][0] / (1LL << gr);
		int y = po[cuuu][1] / (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;
				for (auto l = x[j * (1LL << 31) + k].begin(); l != x[j * (1LL << 31) + k].end(); l++)
				{
					if (num[*l])
						continue;
					int le = *l;
					
					int xxx = (po[cuuu][0] - po[le][0]);
					int yyy = (po[cuuu][1] - po[le][1]);
					int rrr = (-so[i].first + pre[le]);
					if (xxx * xxx + yyy * yyy <= rrr * rrr)
					{
						num[le] = cuuu + 1;
					}
				}
			}
		}
	}
	for (i = 0; i < N; i++)
	{
		cout << num[i] << ' ';
	}
}

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 1 ms 332 KB Output is correct
17 Correct 1 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 4 ms 716 KB Output is correct
22 Correct 17 ms 972 KB Output is correct
23 Correct 17 ms 1032 KB Output is correct
24 Correct 17 ms 1040 KB Output is correct
25 Correct 20 ms 1064 KB Output is correct
26 Correct 18 ms 1040 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 21160 KB Output is correct
2 Correct 207 ms 21156 KB Output is correct
3 Correct 203 ms 20596 KB Output is correct
4 Correct 180 ms 20192 KB Output is correct
5 Correct 573 ms 20988 KB Output is correct
6 Correct 1012 ms 28468 KB Output is correct
7 Correct 581 ms 21876 KB Output is correct
8 Correct 670 ms 23244 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 430 ms 14768 KB Output is correct
3 Correct 2363 ms 42980 KB Output is correct
4 Correct 2417 ms 43088 KB Output is correct
5 Correct 1671 ms 38776 KB Output is correct
6 Correct 616 ms 19376 KB Output is correct
7 Correct 260 ms 10296 KB Output is correct
8 Correct 48 ms 2408 KB Output is correct
9 Correct 2124 ms 42084 KB Output is correct
10 Correct 1451 ms 36588 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2667 ms 43004 KB Output is correct
2 Execution timed out 3093 ms 38428 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 1 ms 332 KB Output is correct
17 Correct 1 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 4 ms 716 KB Output is correct
22 Correct 17 ms 972 KB Output is correct
23 Correct 17 ms 1032 KB Output is correct
24 Correct 17 ms 1040 KB Output is correct
25 Correct 20 ms 1064 KB Output is correct
26 Correct 18 ms 1040 KB Output is correct
27 Correct 8 ms 976 KB Output is correct
28 Correct 8 ms 980 KB Output is correct
29 Correct 7 ms 1060 KB Output is correct
30 Correct 35 ms 1712 KB Output is correct
31 Correct 34 ms 1712 KB Output is correct
32 Correct 36 ms 1648 KB Output is correct
33 Correct 63 ms 7388 KB Output is correct
34 Correct 63 ms 7432 KB Output is correct
35 Correct 78 ms 6984 KB Output is correct
36 Correct 512 ms 14956 KB Output is correct
37 Correct 555 ms 14980 KB Output is correct
38 Correct 497 ms 14812 KB Output is correct
39 Correct 467 ms 14432 KB Output is correct
40 Correct 473 ms 14380 KB Output is correct
41 Correct 478 ms 14388 KB Output is correct
42 Correct 284 ms 11084 KB Output is correct
43 Correct 475 ms 14636 KB Output is correct
44 Correct 460 ms 14656 KB Output is correct
45 Correct 452 ms 14532 KB Output is correct
46 Correct 461 ms 14544 KB Output is correct
47 Correct 465 ms 14544 KB Output is correct
48 Correct 478 ms 14692 KB Output is correct
49 Correct 489 ms 14544 KB Output is correct
50 Correct 493 ms 14704 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 1 ms 332 KB Output is correct
17 Correct 1 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 4 ms 716 KB Output is correct
22 Correct 17 ms 972 KB Output is correct
23 Correct 17 ms 1032 KB Output is correct
24 Correct 17 ms 1040 KB Output is correct
25 Correct 20 ms 1064 KB Output is correct
26 Correct 18 ms 1040 KB Output is correct
27 Correct 188 ms 21160 KB Output is correct
28 Correct 207 ms 21156 KB Output is correct
29 Correct 203 ms 20596 KB Output is correct
30 Correct 180 ms 20192 KB Output is correct
31 Correct 573 ms 20988 KB Output is correct
32 Correct 1012 ms 28468 KB Output is correct
33 Correct 581 ms 21876 KB Output is correct
34 Correct 670 ms 23244 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 430 ms 14768 KB Output is correct
37 Correct 2363 ms 42980 KB Output is correct
38 Correct 2417 ms 43088 KB Output is correct
39 Correct 1671 ms 38776 KB Output is correct
40 Correct 616 ms 19376 KB Output is correct
41 Correct 260 ms 10296 KB Output is correct
42 Correct 48 ms 2408 KB Output is correct
43 Correct 2124 ms 42084 KB Output is correct
44 Correct 1451 ms 36588 KB Output is correct
45 Correct 2667 ms 43004 KB Output is correct
46 Execution timed out 3093 ms 38428 KB Time limit exceeded
47 Halted 0 ms 0 KB -