test/string/run_length_encoding/1.test.cpp

View this file on GitHub
Last update: 2021-08-14 12:12:32+09:00
Problem: https://atcoder.jp/contests/abc143/tasks/abc143_c

Depends on

Run length encoding (include/string/run_length_encoding.hpp)

Code

#define PROBLEM "https://atcoder.jp/contests/abc143/tasks/abc143_c"
#include <iostream>
#include <string>

#include "../../../include/string/run_length_encoding.hpp"

int main() {
  int N;
  std::string S;
  std::cin >> N >> S;
  std::cout << std::size(lib::run_length_encoding(S)) << '\n';
}

#line 1 "test/string/run_length_encoding/1.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc143/tasks/abc143_c"
#include <iostream>
#include <string>

#line 1 "include/string/run_length_encoding.hpp"

//! @file run_length_encoding.hpp

#ifndef CP_LIBRARY_RUN_LENGTH_ENCODING_HPP
#define CP_LIBRARY_RUN_LENGTH_ENCODING_HPP

#line 8 "include/string/run_length_encoding.hpp"
#include <type_traits>
#include <utility>
#include <vector>

#ifndef CP_LIBRARY_WARN
#  if (CP_LIBRARY_DEBUG_LEVEL >= 1)
//! @brief Print warning message
//! @note You can suppress the warning by uncommenting the following line
#    define CP_LIBRARY_WARN(msg) (std::cerr << (msg) << '\n')
// #  define CP_LIBRARY_WARN(msg) (static_cast<void>(0))
#  else
#    define CP_LIBRARY_WARN(msg) (static_cast<void>(0))
#  endif
#  define CP_LIBRARY_WARN_NOT_DEFINED
#endif

namespace lib {

//! @tparam Container container type (deduced from parameter)
//! @param src source container (std::string, std::vector, std::deque, ...)
//! @return A std::vector<std::pair<element type of src, int>> which contains the RLE result.
//! @note Time complexity: O(size(src))
template <typename Container>
[[nodiscard]] auto run_length_encoding(const Container& src) {
  using Elem = std::decay_t<decltype(*std::cbegin(std::declval<Container>()))>;
  if (src.empty()) {
    CP_LIBRARY_WARN("An empty container is provided.");
    return std::vector<std::pair<Elem, int>> {};
  }
  std::vector<std::pair<Elem, int>> res {{*std::cbegin(src), 1}};

  auto iter2 = std::cbegin(src);
  auto iter1 = iter2++;

  for (; iter2 != std::cend(src); std::advance(iter2, 2)) {
    if (*iter1 == *iter2)
      ++res.back().second;
    else
      res.emplace_back(*iter2, 1);
    std::swap(iter1, iter2);
  }
  return res;
}

}  // namespace lib

#ifdef CP_LIBRARY_WARN_NOT_DEFINED
#  undef CP_LIBRARY_WARN
#  undef CP_LIBRARY_WARN_NOT_DEFINED
#  ifdef CP_LIBRARY_WARN
#    undef CP_LIBRARY_WARN
#  endif
#endif

#endif  // CP_LIBRARY_RUN_LENGTH_ENCODING_HPP
#line 6 "test/string/run_length_encoding/1.test.cpp"

int main() {
  int N;
  std::string S;
  std::cin >> N >> S;
  std::cout << std::size(lib::run_length_encoding(S)) << '\n';
}