oj.uz

Submission #404795

# Submission time Handle Problem Language Result Execution time Memory
404795 2021-05-15T02:42:35 Z jjang36524 Circle selection (APIO18_circle_selection) C++14
49 / 100
 3000 ms 261404 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 xx = po[so[i].second][0] / (1LL << gr);
		int y = po[so[i].second][1] / (1LL << gr);
		int j, k;
		for (j = xx - 2; j <= xx + 2; j++)
		{
			for (k = y - 2; k <= y + 2; k++)
			{
				for (auto l = x[j * (1LL << 31) + k].begin(); l != x[j*(1LL<<31)+ k].end(); l++)
				{
					int le = *l;
					if (num[le])
						continue;
					int xxx = (po[so[i].second][0] - po[le][0]);
					int yyy = (po[so[i].second][1] - po[le][1]);
					int rrr = (-so[i].first + pre[le]);
					if (xxx*xxx+yyy*yyy<=rrr*rrr)
					{
						num[le] = so[i].second+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 232 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 5 ms 716 KB Output is correct
21 Correct 4 ms 716 KB Output is correct
22 Correct 31 ms 4000 KB Output is correct
23 Correct 37 ms 4060 KB Output is correct
24 Correct 30 ms 3700 KB Output is correct
25 Correct 33 ms 3896 KB Output is correct
26 Correct 31 ms 4060 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 21224 KB Output is correct
2 Correct 208 ms 21260 KB Output is correct
3 Correct 206 ms 20512 KB Output is correct
4 Correct 181 ms 20196 KB Output is correct
5 Correct 599 ms 21228 KB Output is correct
6 Correct 1621 ms 55888 KB Output is correct
7 Correct 632 ms 23044 KB Output is correct
8 Correct 754 ms 29844 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 1157 ms 68444 KB Output is correct
3 Execution timed out 3080 ms 178424 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 3078 ms 261404 KB Time limit exceeded
2 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 232 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 5 ms 716 KB Output is correct
21 Correct 4 ms 716 KB Output is correct
22 Correct 31 ms 4000 KB Output is correct
23 Correct 37 ms 4060 KB Output is correct
24 Correct 30 ms 3700 KB Output is correct
25 Correct 33 ms 3896 KB Output is correct
26 Correct 31 ms 4060 KB Output is correct
27 Correct 8 ms 968 KB Output is correct
28 Correct 8 ms 1072 KB Output is correct
29 Correct 9 ms 1008 KB Output is correct
30 Correct 67 ms 8400 KB Output is correct
31 Correct 80 ms 8224 KB Output is correct
32 Correct 79 ms 7176 KB Output is correct
33 Correct 67 ms 7344 KB Output is correct
34 Correct 68 ms 7416 KB Output is correct
35 Correct 79 ms 7060 KB Output is correct
36 Correct 1205 ms 73492 KB Output is correct
37 Correct 1355 ms 66408 KB Output is correct
38 Correct 1239 ms 74392 KB Output is correct
39 Correct 561 ms 25944 KB Output is correct
40 Correct 623 ms 25916 KB Output is correct
41 Correct 579 ms 25828 KB Output is correct
42 Correct 274 ms 11208 KB Output is correct
43 Correct 1160 ms 133812 KB Output is correct
44 Correct 1314 ms 133796 KB Output is correct
45 Correct 1135 ms 133636 KB Output is correct
46 Correct 1211 ms 133780 KB Output is correct
47 Correct 1134 ms 133852 KB Output is correct
48 Correct 1119 ms 133860 KB Output is correct
49 Correct 1112 ms 133908 KB Output is correct
50 Correct 1125 ms 133876 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 232 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 5 ms 716 KB Output is correct
21 Correct 4 ms 716 KB Output is correct
22 Correct 31 ms 4000 KB Output is correct
23 Correct 37 ms 4060 KB Output is correct
24 Correct 30 ms 3700 KB Output is correct
25 Correct 33 ms 3896 KB Output is correct
26 Correct 31 ms 4060 KB Output is correct
27 Correct 197 ms 21224 KB Output is correct
28 Correct 208 ms 21260 KB Output is correct
29 Correct 206 ms 20512 KB Output is correct
30 Correct 181 ms 20196 KB Output is correct
31 Correct 599 ms 21228 KB Output is correct
32 Correct 1621 ms 55888 KB Output is correct
33 Correct 632 ms 23044 KB Output is correct
34 Correct 754 ms 29844 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 1157 ms 68444 KB Output is correct
37 Execution timed out 3080 ms 178424 KB Time limit exceeded
38 Halted 0 ms 0 KB -