제출 #491651

#제출 시각아이디문제언어결과실행 시간메모리
491651valerikkSquirrel (RMI18_squirrel)C++17
50 / 100
4809 ms131312 KiB
#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; }

컴파일 시 표준 에러 (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);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...