Submission #352011

#	Time	Username	Problem	Language	Result	Execution time	Memory
352011		KoD	Virus Experiment (JOI19_virus)	C++17	100 / 100	1201 ms	48228 KiB

virus

#line 1 "main.cpp"

/**
 * @title Template
 */

#include <iostream>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>
#include <cassert>

#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"

#line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"

class range {
  struct iter {
    std::size_t itr;
    constexpr iter(std::size_t pos) noexcept: itr(pos) { }
    constexpr void operator ++ () noexcept { ++itr; }
    constexpr bool operator != (iter other) const noexcept { return itr != other.itr; }
    constexpr std::size_t operator * () const noexcept { return itr; }
  };

  struct reviter {
    std::size_t itr;
    constexpr reviter(std::size_t pos) noexcept: itr(pos) { }
    constexpr void operator ++ () noexcept { --itr; }
    constexpr bool operator != (reviter other) const noexcept { return itr != other.itr; }
    constexpr std::size_t operator * () const noexcept { return itr; }
  };

  const iter first, last;

public:
  constexpr range(std::size_t first, std::size_t last) noexcept: first(first), last(std::max(first, last)) { }
  constexpr iter begin() const noexcept { return first; }
  constexpr iter end() const noexcept { return last; }
  constexpr reviter rbegin() const noexcept { return reviter(*last - 1); } 
  constexpr reviter rend() const noexcept { return reviter(*first - 1); } 
};

/**
 * @title Range
 */
#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/random_number.cpp"

#include <cstdint>
#include <random>
#include <chrono>
#line 7 "/Users/kodamankod/Desktop/cpp_programming/Library/other/random_number.cpp"
#include <type_traits>

uint64_t engine() {
  static uint64_t result = static_cast<uint64_t>(std::chrono::system_clock::now().time_since_epoch().count());
  result ^= result << 5;
  result ^= result >> 13;
  result ^= result << 7;
  return result;
}

template <class Integer>
typename std::enable_if<std::is_integral<Integer>::value, Integer>::type random_number(Integer lower, Integer upper) {
  static std::default_random_engine gen(engine());
  return std::uniform_int_distribution<Integer>(lower, upper)(gen);
}

template <class Real>
typename std::enable_if<!std::is_integral<Real>::value, Real>::type random_number(Real lower, Real upper) {
  static std::default_random_engine gen(engine());
  return std::uniform_real_distribution<Real>(lower, upper)(gen);
}

/** 
 * @title Random Number
 */
#line 16 "main.cpp"

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

template <class T>
using Vec = std::vector<T>;

constexpr usize MAX = 800 * 800 + 5;
constexpr std::array<char, 4> LETTER = { 'W', 'E', 'N', 'S' };
constexpr std::array<isize, 4> di = { 0, 0, -1, 1 };
constexpr std::array<isize, 4> dj = { -1, 1, 0, 0 };

int main() {
  usize M, R, C;
  std::cin >> M >> R >> C;
  std::string D;
  std::cin >> D;
  {
    const auto str = D;
    while (D.size() < 200000) {
      D += str;
    }
  }
  Vec<Vec<usize>> strength(R, Vec<usize>(C));
  for (auto &v: strength) {
    for (auto &x: v) {
      std::cin >> x;
    }
  }
  std::array<usize, (1 << 4)> max{};
  for (auto set: range(0, 1 << 4)) {
    usize cur = 0;
    for (const auto c: D) {
      bool ok = false;
      for (auto i: range(0, 4)) {
        if ((set >> i & 1) == 1 && LETTER[i] == c) {
          ok = true;
          break;
        }
      }
      if (ok) {
        cur += 1;
      }
      else {
        cur = 0;
      }
      max[set] = std::max(max[set], cur);
    }
  }
  Vec<std::pair<usize, usize>> cell(R * C);
  for (auto i: range(0, R)) {
    for (auto j: range(0, C)) {
      cell[i * C + j] = std::make_pair(i, j);
    }
  }
  {
    std::default_random_engine gen(engine());
    std::shuffle(cell.begin(), cell.end(), gen);
  }
  Vec<Vec<usize>> ans(R, Vec<usize>(C, MAX));
  Vec<Vec<bool>> visited(R, Vec<bool>(C));
  Vec<Vec<bool>> done(R, Vec<bool>(C));
  const auto inside = [&](const isize i, const isize j) {
    return 0 <= i && i < (isize) R && 0 <= j && j < (isize) C;
  };
  const auto check = [&](const isize i, const isize j) {
    if (!inside(i, j) || strength[i][j] == 0) {
      return false;
    }
    usize set = 0;
    for (auto k: range(0, 4)) {
      const auto ni = i + di[k];
      const auto nj = j + dj[k];
      if (inside(ni, nj) && visited[ni][nj]) {
        set |= 1 << k;
      }
    }
    return max[set] >= strength[i][j];
  };
  for (const auto [si, sj]: cell) {
    if (strength[si][sj] == 0) {
      continue;
    }
    done[si][sj] = true;
    Vec<std::pair<isize, isize>> que;
    visited[si][sj] = true;
    que.emplace_back(si, sj);
    bool consider = true;
    for (usize idx = 0; idx < que.size(); ++idx) {
      const auto [i, j] = que[idx];
      for (auto k: range(0, 4)) {
        const auto ni = i + di[k];
        const auto nj = j + dj[k];
        if (check(ni, nj) && !visited[ni][nj]) {
          if (done[ni][nj]) {
            consider = false;
            break;
          }
          visited[ni][nj] = true;
          que.emplace_back(ni, nj);
        }
      }
      if (!consider) {
        break;
      }
    }
    if (consider) {
      for (const auto [i, j]: que) {
        ans[i][j] = std::min(ans[i][j], que.size());
      }
    }
    for (const auto [i, j]: que) {
      visited[i][j] = false;
    }
  }
  usize val = MAX, cnt = 0;
  for (const auto &v: ans) {
    for (const auto x: v) {
      if (val > x) {
        val = x;
        cnt = 0;
      }
      if (val == x) {
        cnt += 1;
      }
    }
  }
  std::cout << val << '\n';
  std::cout << cnt << '\n';
  return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 6 / 6
• Subtask 3: 80 / 80