oj.uz

Submission #491650

# Submission time Handle Problem Language Result Execution time Memory
491650 2021-12-03T17:08:40 Z valerikk Squirrel (RMI18_squirrel) C++17
25 / 100
 4700 ms 41664 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

const int MAX_FRACTAL_SIZE = 1024;

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

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

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 41468 KB Output is correct
2 Correct 129 ms 41508 KB Output is correct
3 Correct 2144 ms 41512 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3595 ms 41584 KB Output is correct
2 Correct 3469 ms 41480 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4753 ms 41608 KB Time limit exceeded
2 Execution timed out 4759 ms 41580 KB Time limit exceeded
3 Execution timed out 4746 ms 41572 KB Time limit exceeded
4 Execution timed out 4760 ms 41512 KB Time limit exceeded
5 Execution timed out 4791 ms 41468 KB Time limit exceeded

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4800 ms 41544 KB Time limit exceeded
2 Execution timed out 4798 ms 41484 KB Time limit exceeded
3 Execution timed out 4791 ms 41476 KB Time limit exceeded
4 Execution timed out 4798 ms 41468 KB Time limit exceeded
5 Execution timed out 4799 ms 41540 KB Time limit exceeded
6 Execution timed out 4782 ms 41664 KB Time limit exceeded
7 Execution timed out 4801 ms 41616 KB Time limit exceeded
8 Execution timed out 4765 ms 41488 KB Time limit exceeded
9 Execution timed out 4799 ms 41468 KB Time limit exceeded
10 Execution timed out 4801 ms 41548 KB Time limit exceeded