oj.uz

Submission #352011

# Submission time Handle Problem Language Result Execution time Memory
352011 2021-01-20T11:05:56 Z KoD Virus Experiment (JOI19_virus) C++17
100 / 100
 1201 ms 48228 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 768 KB Output is correct
2 Correct 416 ms 22264 KB Output is correct
3 Correct 703 ms 24560 KB Output is correct
4 Correct 609 ms 22264 KB Output is correct
5 Correct 563 ms 24828 KB Output is correct
6 Correct 18 ms 764 KB Output is correct
7 Correct 634 ms 22304 KB Output is correct
8 Correct 168 ms 9996 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 636 KB Output is correct
2 Correct 27 ms 876 KB Output is correct
3 Correct 37 ms 876 KB Output is correct
4 Correct 22 ms 876 KB Output is correct
5 Correct 36 ms 876 KB Output is correct
6 Correct 38 ms 876 KB Output is correct
7 Correct 26 ms 636 KB Output is correct
8 Correct 37 ms 876 KB Output is correct
9 Correct 26 ms 636 KB Output is correct
10 Correct 25 ms 896 KB Output is correct
11 Correct 28 ms 784 KB Output is correct
12 Correct 27 ms 760 KB Output is correct
13 Correct 39 ms 876 KB Output is correct
14 Correct 38 ms 876 KB Output is correct
15 Correct 36 ms 876 KB Output is correct
16 Correct 38 ms 876 KB Output is correct
17 Correct 37 ms 748 KB Output is correct
18 Correct 33 ms 748 KB Output is correct
19 Correct 38 ms 876 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 768 KB Output is correct
2 Correct 416 ms 22264 KB Output is correct
3 Correct 703 ms 24560 KB Output is correct
4 Correct 609 ms 22264 KB Output is correct
5 Correct 563 ms 24828 KB Output is correct
6 Correct 18 ms 764 KB Output is correct
7 Correct 634 ms 22304 KB Output is correct
8 Correct 168 ms 9996 KB Output is correct
9 Correct 24 ms 636 KB Output is correct
10 Correct 27 ms 876 KB Output is correct
11 Correct 37 ms 876 KB Output is correct
12 Correct 22 ms 876 KB Output is correct
13 Correct 36 ms 876 KB Output is correct
14 Correct 38 ms 876 KB Output is correct
15 Correct 26 ms 636 KB Output is correct
16 Correct 37 ms 876 KB Output is correct
17 Correct 26 ms 636 KB Output is correct
18 Correct 25 ms 896 KB Output is correct
19 Correct 28 ms 784 KB Output is correct
20 Correct 27 ms 760 KB Output is correct
21 Correct 39 ms 876 KB Output is correct
22 Correct 38 ms 876 KB Output is correct
23 Correct 36 ms 876 KB Output is correct
24 Correct 38 ms 876 KB Output is correct
25 Correct 37 ms 748 KB Output is correct
26 Correct 33 ms 748 KB Output is correct
27 Correct 38 ms 876 KB Output is correct
28 Correct 1097 ms 38916 KB Output is correct
29 Correct 1165 ms 48228 KB Output is correct
30 Correct 1025 ms 34884 KB Output is correct
31 Correct 1014 ms 29788 KB Output is correct
32 Correct 939 ms 23916 KB Output is correct
33 Correct 559 ms 22548 KB Output is correct
34 Correct 1201 ms 47256 KB Output is correct
35 Correct 820 ms 25460 KB Output is correct
36 Correct 783 ms 22520 KB Output is correct
37 Correct 1085 ms 29984 KB Output is correct
38 Correct 1041 ms 38760 KB Output is correct
39 Correct 507 ms 23308 KB Output is correct
40 Correct 565 ms 23280 KB Output is correct
41 Correct 545 ms 22284 KB Output is correct
42 Correct 936 ms 33180 KB Output is correct
43 Correct 1043 ms 29736 KB Output is correct
44 Correct 197 ms 9996 KB Output is correct