oj.uz

Submission #404798

# Submission time Handle Problem Language Result Execution time Memory
404798 2021-05-15T02:44:29 Z jjang36524 Circle selection (APIO18_circle_selection) C++14
37 / 100
 3000 ms 411636 KB 
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
#define int long long
using namespace std;
unordered_map<int, vector<int>>x[31];
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++)
	{
		int j;
		for (j = 0; j <= 30; j++)
		{
			x[j][po[i][0] / (1LL << j) * (1LL << 31) + po[i][1] / (1LL << j)].push_back(i);
		}
		
	}
	for (i = 0; i < N; i++)
	{
		if (num[so[i].second])
			continue;
		while ((1LL << gr) >= -so[i].first*2)
		{
			gr--;
			
		}
		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++)
			{
				if (!x[gr].count(j * (1LL << 31) + k))
					continue;
				for (auto l = x[gr][j * (1LL << 31) + k].begin(); l != x[gr][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 2 ms 588 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 2 ms 588 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 9 ms 2656 KB Output is correct
17 Correct 8 ms 2380 KB Output is correct
18 Correct 9 ms 2456 KB Output is correct
19 Correct 52 ms 10500 KB Output is correct
20 Correct 38 ms 8652 KB Output is correct
21 Correct 53 ms 11244 KB Output is correct
22 Correct 56 ms 10588 KB Output is correct
23 Correct 54 ms 9852 KB Output is correct
24 Correct 58 ms 10808 KB Output is correct
25 Correct 66 ms 11584 KB Output is correct
26 Correct 61 ms 11140 KB Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2685 ms 226776 KB Output is correct
3 Execution timed out 3109 ms 409412 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 3083 ms 411636 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 2 ms 588 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 2 ms 588 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 9 ms 2656 KB Output is correct
17 Correct 8 ms 2380 KB Output is correct
18 Correct 9 ms 2456 KB Output is correct
19 Correct 52 ms 10500 KB Output is correct
20 Correct 38 ms 8652 KB Output is correct
21 Correct 53 ms 11244 KB Output is correct
22 Correct 56 ms 10588 KB Output is correct
23 Correct 54 ms 9852 KB Output is correct
24 Correct 58 ms 10808 KB Output is correct
25 Correct 66 ms 11584 KB Output is correct
26 Correct 61 ms 11140 KB Output is correct
27 Correct 134 ms 20992 KB Output is correct
28 Correct 128 ms 20176 KB Output is correct
29 Correct 130 ms 20964 KB Output is correct
30 Correct 138 ms 20216 KB Output is correct
31 Correct 138 ms 20164 KB Output is correct
32 Correct 148 ms 20936 KB Output is correct
33 Correct 2204 ms 201540 KB Output is correct
34 Correct 2263 ms 209928 KB Output is correct
35 Correct 2221 ms 205892 KB Output is correct
36 Correct 2434 ms 205008 KB Output is correct
37 Correct 2503 ms 211580 KB Output is correct
38 Correct 2501 ms 206972 KB Output is correct
39 Correct 611 ms 48668 KB Output is correct
40 Correct 607 ms 48884 KB Output is correct
41 Correct 602 ms 48800 KB Output is correct
42 Correct 1132 ms 106404 KB Output is correct
43 Correct 2023 ms 162652 KB Output is correct
44 Correct 1974 ms 162884 KB Output is correct
45 Correct 1952 ms 162692 KB Output is correct
46 Correct 1983 ms 162816 KB Output is correct
47 Correct 1967 ms 162748 KB Output is correct
48 Correct 1990 ms 162832 KB Output is correct
49 Correct 1995 ms 162844 KB Output is correct
50 Correct 2089 ms 162596 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 2 ms 588 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 2 ms 588 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 9 ms 2656 KB Output is correct
17 Correct 8 ms 2380 KB Output is correct
18 Correct 9 ms 2456 KB Output is correct
19 Correct 52 ms 10500 KB Output is correct
20 Correct 38 ms 8652 KB Output is correct
21 Correct 53 ms 11244 KB Output is correct
22 Correct 56 ms 10588 KB Output is correct
23 Correct 54 ms 9852 KB Output is correct
24 Correct 58 ms 10808 KB Output is correct
25 Correct 66 ms 11584 KB Output is correct
26 Correct 61 ms 11140 KB Output is correct
27 Execution timed out 3106 ms 388080 KB Time limit exceeded
28 Halted 0 ms 0 KB -