제출 #964583

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
964583		kilkuwu	육각형 영역 (APIO21_hexagon)	C++17	20 / 100	467 ms	211880 KiB

hexagon

#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;
      |       ^~~

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 11 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 15
• Subtask 6: 0 / 19
• Subtask 7: 0 / 18
• Subtask 8: 0 / 16