oj.uz

Submission #964583

# Submission time Handle Problem Language Result Execution time Memory
964583 2024-04-17T07:00:48 Z kilkuwu Hexagonal Territory (APIO21_hexagon) C++17
20 / 100
 467 ms 211880 KB 
#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;
}

Compilation message

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 71404 KB Output is correct
2 Correct 12 ms 71224 KB Output is correct
3 Correct 12 ms 71260 KB Output is correct
4 Correct 10 ms 71256 KB Output is correct
5 Correct 10 ms 71260 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 71260 KB Output is correct
2 Correct 10 ms 71416 KB Output is correct
3 Correct 10 ms 71440 KB Output is correct
4 Correct 11 ms 71256 KB Output is correct
5 Correct 10 ms 71260 KB Output is correct
6 Correct 10 ms 71260 KB Output is correct
7 Correct 10 ms 71368 KB Output is correct
8 Correct 10 ms 71260 KB Output is correct
9 Correct 10 ms 71380 KB Output is correct
10 Correct 11 ms 71260 KB Output is correct
11 Correct 10 ms 71256 KB Output is correct
12 Correct 11 ms 71512 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 211640 KB Output is correct
2 Correct 332 ms 211280 KB Output is correct
3 Correct 311 ms 211392 KB Output is correct
4 Correct 334 ms 211428 KB Output is correct
5 Correct 337 ms 211536 KB Output is correct
6 Correct 341 ms 211620 KB Output is correct
7 Correct 366 ms 211528 KB Output is correct
8 Correct 369 ms 211552 KB Output is correct
9 Correct 378 ms 211536 KB Output is correct
10 Correct 362 ms 211476 KB Output is correct
11 Correct 330 ms 211568 KB Output is correct
12 Correct 375 ms 210428 KB Output is correct
13 Correct 367 ms 210468 KB Output is correct
14 Correct 350 ms 210456 KB Output is correct
15 Correct 321 ms 211496 KB Output is correct
16 Correct 366 ms 211700 KB Output is correct
17 Correct 392 ms 211644 KB Output is correct
18 Correct 10 ms 71464 KB Output is correct
19 Correct 11 ms 71260 KB Output is correct
20 Correct 12 ms 71256 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 376 ms 211880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 71260 KB Output is correct
2 Correct 11 ms 71428 KB Output is correct
3 Incorrect 350 ms 211660 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 211544 KB Output is correct
2 Correct 360 ms 211292 KB Output is correct
3 Correct 375 ms 211392 KB Output is correct
4 Correct 374 ms 211456 KB Output is correct
5 Correct 347 ms 211612 KB Output is correct
6 Correct 467 ms 211696 KB Output is correct
7 Correct 351 ms 211400 KB Output is correct
8 Correct 361 ms 211536 KB Output is correct
9 Correct 336 ms 211592 KB Output is correct
10 Correct 354 ms 211468 KB Output is correct
11 Correct 357 ms 211852 KB Output is correct
12 Correct 324 ms 210624 KB Output is correct
13 Correct 330 ms 210776 KB Output is correct
14 Correct 361 ms 210380 KB Output is correct
15 Correct 330 ms 211560 KB Output is correct
16 Correct 334 ms 211536 KB Output is correct
17 Correct 344 ms 211540 KB Output is correct
18 Incorrect 344 ms 211872 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #7
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 71260 KB Output is correct
2 Correct 10 ms 71260 KB Output is correct
3 Correct 11 ms 71260 KB Output is correct
4 Correct 10 ms 71216 KB Output is correct
5 Runtime error 83 ms 144464 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 211496 KB Output is correct
2 Correct 10 ms 71256 KB Output is correct
3 Correct 10 ms 71220 KB Output is correct
4 Correct 9 ms 71260 KB Output is correct
5 Correct 10 ms 71256 KB Output is correct
6 Correct 341 ms 211428 KB Output is correct
7 Correct 356 ms 211636 KB Output is correct
8 Correct 347 ms 211428 KB Output is correct
9 Correct 339 ms 211544 KB Output is correct
10 Correct 326 ms 211632 KB Output is correct
11 Correct 341 ms 211400 KB Output is correct
12 Correct 351 ms 211536 KB Output is correct
13 Correct 320 ms 211656 KB Output is correct
14 Correct 345 ms 211768 KB Output is correct
15 Correct 364 ms 211456 KB Output is correct
16 Correct 363 ms 210600 KB Output is correct
17 Correct 330 ms 210484 KB Output is correct
18 Correct 373 ms 210400 KB Output is correct
19 Correct 356 ms 211520 KB Output is correct
20 Correct 341 ms 211648 KB Output is correct
21 Correct 340 ms 211524 KB Output is correct
22 Incorrect 354 ms 211656 KB Output isn't correct
23 Halted 0 ms 0 KB -