Submission #491651

#	Time	Username	Problem	Language	Result	Execution time	Memory
491651		valerikk	Squirrel (RMI18_squirrel)	C++17	50 / 100	4809 ms	131312 KiB

squirrel

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

const int MAX_FRACTAL_SIZE = 1024;
const int GCD_TABLE_SIZE = 5000;

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

void build_jumps() {
	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);
		}
	}
}

int gcd_table[GCD_TABLE_SIZE + 1][GCD_TABLE_SIZE + 1];

void build_gcd_table() {
	for (int a = 0; a <= GCD_TABLE_SIZE; ++a) {
		for (int b = a; b <= GCD_TABLE_SIZE; ++b) {
			gcd_table[a][b] = gcd_table[b][a] = (a == 0 || b == 0 ? a + b : gcd_table[b - a][a]);
		}
	}
}

int gcd(int a, int b) {
	while (b != 0 && b > GCD_TABLE_SIZE) {
		a %= b;
		std::swap(a, b);
	}
	return (b == 0 ? a : gcd_table[a % b][b]);
}

int main() {
	build_jumps();
	build_gcd_table();

	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 += gcd(x, y) == 1;
		for (const auto &[dx, dy] : jumps[fractal_size]) {
			answer += gcd(x - dx, y - dy) == 1;
		}
	}
	printf("%d\n", answer);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 15 / 15
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 0 / 50