oj.uz

Submission #491655

# Submission time Handle Problem Language Result Execution time Memory
491655 2021-12-03T17:26:48 Z valerikk Squirrel (RMI18_squirrel) C++17
100 / 100
 4331 ms 131444 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

const int MAX_FRACTAL_SIZE = 1024;
const int MAX_NUMBER = 10000;

std::vector<std::pair<int, int>> jumps[MAX_FRACTAL_SIZE + 1];

bool visible[MAX_NUMBER + 1][MAX_NUMBER + 1];

bool is_visible(int a, int b) {
	if (!(a & 1) && !(b & 1)) {
		return false;
	}
	while (b != 0 && b > MAX_NUMBER) {
		a %= b;
		std::swap(a, b);
	}
	return b == 0 ? a <= 1 : visible[a % b][b];
}

int main() {
	jumps[1] = {{1, 0}};
	for (int fractal_size = 2; fractal_size <= MAX_FRACTAL_SIZE; fractal_size *= 2) {
		for (int i = 1; i <= fractal_size; ++i) {
			jumps[fractal_size].emplace_back(i, 0);
		}
		for (int i = 1; i <= fractal_size / 2; ++i) {
			jumps[fractal_size].emplace_back(fractal_size + i, i);
		}
		for (int i = 1; i <= fractal_size / 2; ++i) {
			jumps[fractal_size].emplace_back(fractal_size + i, -i);
		}
		for (const auto &[x, y] : jumps[fractal_size / 2]) {
			jumps[fractal_size].emplace_back(fractal_size + fractal_size / 2 + x, fractal_size / 2 + y);
			jumps[fractal_size].emplace_back(fractal_size + fractal_size / 2 + x, -fractal_size / 2 + y);
			jumps[fractal_size].emplace_back(fractal_size + fractal_size / 2 + y, fractal_size / 2 + x);
			jumps[fractal_size].emplace_back(fractal_size + fractal_size / 2 - y, -fractal_size / 2 - x);
		}
	}

	for (int a = 0; a <= MAX_NUMBER; ++a) {
		for (int b = a; b <= MAX_NUMBER; ++b) {
			visible[a][b] = visible[b][a] = (a == 0 ? b <= 1 : visible[a][b - a]);
		}
	}

	int N, M, F;
	scanf("%d%d%d", &N, &M, &F);
	int answer = 0;
	while (F--) {
		int x, y, fractal_size;
		scanf("%d%d%d", &x, &y, &fractal_size);
		--x;
		--y;
		answer += is_visible(x, y);
		for (const auto &[dx, dy] : jumps[fractal_size]) {
			answer += is_visible(x - dx, y - dy);
		}
	}
	printf("%d\n", answer);
	return 0;
}

Compilation message

squirrel.cpp: In function 'int main()':
squirrel.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |  scanf("%d%d%d", &N, &M, &F);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
squirrel.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   scanf("%d%d%d", &x, &y, &fractal_size);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 131180 KB Output is correct
2 Correct 439 ms 131140 KB Output is correct
3 Correct 872 ms 131160 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1282 ms 131116 KB Output is correct
2 Correct 1306 ms 131072 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1789 ms 131124 KB Output is correct
2 Correct 1821 ms 131224 KB Output is correct
3 Correct 2048 ms 131156 KB Output is correct
4 Correct 1917 ms 131444 KB Output is correct
5 Correct 1955 ms 131140 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3233 ms 131136 KB Output is correct
2 Correct 3178 ms 131084 KB Output is correct
3 Correct 3629 ms 131152 KB Output is correct
4 Correct 3587 ms 131068 KB Output is correct
5 Correct 4065 ms 131232 KB Output is correct
6 Correct 3728 ms 131064 KB Output is correct
7 Correct 4138 ms 131096 KB Output is correct
8 Correct 4266 ms 131168 KB Output is correct
9 Correct 3985 ms 131120 KB Output is correct
10 Correct 4331 ms 131348 KB Output is correct