제출 #964583

#제출 시각아이디문제언어결과실행 시간메모리
964583kilkuwu육각형 영역 (APIO21_hexagon)C++17
20 / 100
467 ms211880 KiB
#include "hexagon.h" #include <bits/stdc++.h> template <int md> struct Modular { int v; constexpr Modular() : v(0) {} template <typename T> static inline int normalize(const T& x) { int res = -md <= x && x < md ? static_cast<int>(x) : static_cast<int>(x % md); return res + (res < 0) * md; } static constexpr int mod() { return md; } template <typename U> Modular(const U& x) : v(normalize(x)) {} const int& operator()() const { return v; } template <typename U> explicit operator U() const { return static_cast<U>(v); } using M = Modular; constexpr static inline M _raw(int x) { static_assert(x >= 0 && x < md); M res; res.v = x; return res; } template <typename U> friend std::enable_if_t<std::is_integral_v<U>, M> power(M b, U e) { assert(e >= 0); M ans = 1; while (e) { if (e & 1) ans *= b; b *= b; e >>= 1; } return ans; } M inv() const { M res = power(*this, md - 2); return res; } M& operator+=(const M& y) { return v += y.v, v -= (v >= md) * md, *this; } M& operator-=(const M& y) { return v -= y.v, v += (v < 0) * md, *this; } M& operator*=(const M& y) { return v = (int64_t) v * y.v % md, *this; } M& operator/=(const M& y) { return *this *= y.inv(); } M& operator++() { return *this += _raw(1); } M& operator--() { return *this -= _raw(1); } M operator++(int) { M res(*this); return *this += _raw(1), res; } M operator--(int) { M res(*this); return *this -= _raw(1), res; } M operator-() const { return M(-v); } friend bool operator==(const M& x, const M& y) { return x.v == y.v; } friend bool operator<(const M& x, const M& y) { return x.v < y.v; } friend bool operator>(const M& x, const M& y) { return x.v > y.v; } friend bool operator<=(const M& x, const M& y) { return x.v <= y.v; } friend bool operator>=(const M& x, const M& y) { return x.v >= y.v; } friend bool operator!=(const M& x, const M& y) { return x.v != y.v; } template <typename Istream> friend Istream& operator>>(Istream& is, M& y) { int64_t x; is >> x; y.v = y.normalize(x); return is; } template <typename Ostream> friend Ostream& operator<<(Ostream& os, const M& y) { return os << y.v; } friend M operator+(const M& x, const M& y) { return M(x) += y; } friend M operator-(const M& x, const M& y) { return M(x) -= y; } friend M operator*(const M& x, const M& y) { return M(x) *= y; } friend M operator/(const M& x, const M& y) { return M(x) /= y; } }; constexpr int md = 1e9 + 7; using Mint = Modular<md>; constexpr int A = 4200; int grid[A][A]; std::bitset<A> is_road[A]; std::pair<int, int> q[A * A]; int sz = 0, fi = 0; std::bitset<A> vis[A]; int dist[A][A]; const std::vector<std::pair<int, int>> dxy = { {-1, 0}, {0, 1}, {1, 1}, {1, 0}, {0, -1}, {-1, -1} }; int draw_territory(int N, int a, int b, std::vector<int> D, std::vector<int> L) { memset(grid, -1, sizeof(grid)); if (N == 3) { Mint answer = 0; Mint size = L[0] + 1; Mint number = size * (size + 1) / 2; answer = size * (size + 1) * (size * 2 + 1) / 6; answer -= number; answer = number * a + b * answer; return (int) answer; } // middle point is [2100, 2100]; // we just make a queue or sth int sx = 2100, sy = 2100; is_road[sx][sy] = 1; for (int i = 0; i < N; i++) { auto [dx, dy] = dxy[D[i] - 1]; for (int j = 0; j < L[i]; j++) { sx += dx, sy += dy; is_road[sx][sy] = 1; } } for (int i = 0; i < A; i++) { if (!vis[0][i]) { vis[0][i] = 1; q[sz++] = {0, i}; } if (!vis[i][0]) { vis[i][0] = 1; q[sz++] = {i, 0}; } if (!vis[A - 1][i]) { vis[A - 1][i] = 1; q[sz++] = {A - 1, i}; } if (!vis[i][A - 1]) { vis[i][A - 1] = 1; q[sz++] = {i, A - 1}; } } auto bounded = [&](int x, int y) { return 0 <= x && x < A && 0 <= y && y < A; }; while (fi < sz) { auto [x, y] = q[fi++]; for (auto [dx, dy] : dxy) { int nx = x + dx, ny = y + dy; if (!bounded(nx, ny)) continue; if (is_road[nx][ny]) continue; if (vis[nx][ny]) continue; vis[nx][ny] = 1; q[sz++] = {nx, ny}; } } sz = 0, fi = 0; q[sz++] = {2100, 2100}; grid[2100][2100] = 0; int cnt = 0; Mint ans = 0; while (fi < sz) { auto [x, y] = q[fi++]; ans += a + Mint(b) * grid[x][y]; for (auto [dx, dy] : dxy) { int nx = x + dx, ny = y + dy; if (!bounded(nx, ny)) continue; if (vis[nx][ny]) continue; if (grid[nx][ny] == -1) { grid[nx][ny] = grid[x][y] + 1; q[sz++] = {nx, ny}; } } } return (int) ans; }

컴파일 시 표준 에러 (stderr) 메시지

hexagon.cpp: In function 'int draw_territory(int, int, int, std::vector<int>, std::vector<int>)':
hexagon.cpp:191:7: warning: unused variable 'cnt' [-Wunused-variable]
  191 |   int cnt = 0;
      |       ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...