test/atcoder/abc259_c.test.cpp

View this file on GitHub
Last update: 2023-08-11 19:35:51+09:00
Problem: https://atcoder.jp/contests/abc259/tasks/abc259_c

Depends on

Code

// verification-helper: PROBLEM https://atcoder.jp/contests/abc259/tasks/abc259_c

#include "src/cpp-template/header/change-min.hpp"
#include "src/cpp-template/header/rep.hpp"
#include "src/cpp-template/header/size-alias.hpp"
#include "src/sequence/run-length-encoding.hpp"

#include <algorithm>
#include <iostream>
#include <string>

namespace luz {

  void main_() {
    std::string s, t;
    std::cin >> s >> t;

    auto ss = run_length_encoding(s);
    auto ts = run_length_encoding(t);

    usize n = std::min(ss.size(), ts.size());
    for (usize i: rep(0, n)) {
      auto &[sc, scnt] = ss[i];
      auto &[tc, tcnt] = ts[i];

      if (scnt >= 2) {
        chmin(tcnt, scnt);
      }
    }

    if (ss == ts) {
      std::cout << "Yes" << std::endl;
    } else {
      std::cout << "No" << std::endl;
    }
  }

} // namespace luz

int main() {
  luz::main_();
}

#line 1 "test/atcoder/abc259_c.test.cpp"
// verification-helper: PROBLEM https://atcoder.jp/contests/abc259/tasks/abc259_c

#line 2 "src/cpp-template/header/change-min.hpp"

namespace luz {

  template < typename T1, typename T2 >
  inline bool chmin(T1 &a, T2 b) {
    return a > b and (a = b, true);
  }

} // namespace luz
#line 2 "src/cpp-template/header/rep.hpp"

#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

} // namespace luz
#line 4 "src/cpp-template/header/rep.hpp"

#include <algorithm>

namespace luz {

  struct rep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        ++i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rep(const usize f, const usize l) noexcept
        : f(std::min(f, l)),
          l(l) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

  struct rrep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        --i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rrep(const usize f, const usize l) noexcept
        : f(l - 1),
          l(std::min(f, l) - 1) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

} // namespace luz
#line 2 "src/sequence/run-length-encoding.hpp"

#line 4 "src/sequence/run-length-encoding.hpp"

#include <string>
#include <utility>
#include <vector>

namespace luz {

  template < class T, class Iter >
  std::vector< std::pair< T, usize > > run_length_encoding(
      Iter first, Iter last) {
    std::vector< std::pair< T, usize > > result;

    while (first != last) {
      if (result.empty() or result.back().first != *first) {
        result.emplace_back(*first, 0);
      }

      result.back().second++;
      ++first;
    }

    return result;
  }

  template < typename T >
  std::vector< std::pair< T, usize > > run_length_encoding(
      const std::vector< T > &vs) {
    return run_length_encoding(vs.begin(), vs.end());
  }

  std::vector< std::pair< char, usize > > run_length_encoding(
      const std::string &s) {
    return run_length_encoding< char >(s.begin(), s.end());
  }

} // namespace luz
#line 7 "test/atcoder/abc259_c.test.cpp"

#line 9 "test/atcoder/abc259_c.test.cpp"
#include <iostream>
#line 11 "test/atcoder/abc259_c.test.cpp"

namespace luz {

  void main_() {
    std::string s, t;
    std::cin >> s >> t;

    auto ss = run_length_encoding(s);
    auto ts = run_length_encoding(t);

    usize n = std::min(ss.size(), ts.size());
    for (usize i: rep(0, n)) {
      auto &[sc, scnt] = ss[i];
      auto &[tc, tcnt] = ts[i];

      if (scnt >= 2) {
        chmin(tcnt, scnt);
      }
    }

    if (ss == ts) {
      std::cout << "Yes" << std::endl;
    } else {
      std::cout << "No" << std::endl;
    }
  }

} // namespace luz

int main() {
  luz::main_();
}