cp-documentation

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub zawa-tin/cp-documentation

:heavy_check_mark: Test/Manual/agc026_a.test.cpp

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#include "../../Src/Sequence/RunLengthEncoding.hpp"

#include <vector>
#include <iostream>

/*
 * AGC026-A Colorful Slimes 2
 * https://atcoder.jp/contests/agc026/submissions/45973756
 */

void solve() {
    int n; std::cin >> n;
    std::vector<int> a(n);
    for (auto& x : a) std::cin >> x;
    zawa::RunLengthEncoding rle(a);
    int ans{};
    for (const auto& x : rle) ans += x.number() / 2;
    std::cout << ans << std::endl;
}

int main() {
#ifdef ATCODER
    solve();
#else
    std::cout << "Hello World" << std::endl;
#endif
}
#line 1 "Test/Manual/agc026_a.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#line 2 "Src/Sequence/RunLengthEncoding.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Sequence/RunLengthEncoding.hpp"

#include <deque>
#include <vector>
#include <cassert>

namespace zawa {

template <class Value, class Number = u64>
class RunLengthEncoding {
public:
    class Data {
    private:
        Value value_;
        Number number_;
    public:
        Data() = default;
        Data(const Value& value, Number number) : value_{ value }, number_{ number } {}

        const Value& value() const noexcept {
            return value_;
        }

        Number number() const noexcept {
            return number_;
        }

        friend RunLengthEncoding;
    };

private:
    std::deque<Data> seq_;
    u64 sum_{};

    template <class InputIterator>
    inline void build(InputIterator first, InputIterator last) {
        for (auto it{ first } ; it != last ; it++) {
            if (seq_.empty() or seq_.back().value() != *it) {
                seq_.emplace_back(*it, Number{1});
            }
            else {
                seq_.back().number_++;
            }
            sum_++;
        }
    }

public:
    RunLengthEncoding() = default;

    template <class InputIterator>
    RunLengthEncoding(InputIterator first, InputIterator last) {
        build(first, last);
    }

    RunLengthEncoding(const std::vector<Value>& a) {
        build(a.begin(), a.end());
    }

    constexpr usize size() const noexcept {
        return seq_.size();
    }

    constexpr u64 sum() const noexcept {
        return sum_;
    }

    const Data& operator[](u32 i) const noexcept {
        assert(i < size());
        return seq_[i];
    }

    const Value& value(u32 i) const noexcept {
        assert(i < size());
        return seq_[i].value();
    }

    const Number number(u32 i) const noexcept {
        assert(i < size());
        return seq_[i].number();
    }

    typename decltype(seq_)::const_iterator begin() const noexcept {
        return seq_.begin();
    }

    typename decltype(seq_)::const_iterator end() const noexcept {
        return seq_.end();
    }

    const Data& front() const noexcept {
        assert(size());
        return seq_.front();
    }

    const Data& back() const noexcept {
        assert(size());
        return seq_.back();
    }

    void pushBack(const Value& value, const Number number = Number{1}) {
        sum_ += number;
        if (seq_.empty() or seq_.back().value() != value) {
            seq_.emplace_back(value, number);
        }
        else {
            seq_.back().number_ += number;
        }
    }

    void pushFront(const Value& value, const Number number = Number{1}) {
        sum_ += number;
        if (seq_.empty() or seq_.front().value() != value) {
            seq_.emplace_front(value, number);
        }
        else {
            seq_.front().number_ += number;
        }
    }

    void popBack() {
        assert(size());
        sum_ -= seq_.back().number();
        seq_.pop_back();
    }

    void popFront() {
        assert(size());
        sum_ -= seq_.front().number();
        seq_.pop_front();
    }

    std::vector<Data> popBack(u64 number) {
        assert(number <= sum());
        sum_ -= number;
        std::vector<Data> res;
        while (number and number >= seq_.back().number()) {
            res.push_back(seq_.back());
            number -= seq_.back().number();
            seq_.pop_back();
        }
        if (number) {
            res.emplace_back(seq_.back().value(), number);
            seq_.back().number_ -= number;
        }
        return res;
    }

    std::vector<Data> popFront(u64 number) {
        assert(number <= sum());
        sum_ -= number;
        std::vector<Data> res;
        while (number and number >= seq_.front().number()) {
            res.push_back(seq_.front());
            number -= seq_.front().number();
            seq_.pop_front();
        }
        if (number) {
            res.emplace_back(seq_.front().value(), number);
            seq_.front().number_ -= number;
        }
        return res;
    }
};

} // namespace zawa
#line 4 "Test/Manual/agc026_a.test.cpp"

#line 6 "Test/Manual/agc026_a.test.cpp"
#include <iostream>

/*
 * AGC026-A Colorful Slimes 2
 * https://atcoder.jp/contests/agc026/submissions/45973756
 */

void solve() {
    int n; std::cin >> n;
    std::vector<int> a(n);
    for (auto& x : a) std::cin >> x;
    zawa::RunLengthEncoding rle(a);
    int ans{};
    for (const auto& x : rle) ans += x.number() / 2;
    std::cout << ans << std::endl;
}

int main() {
#ifdef ATCODER
    solve();
#else
    std::cout << "Hello World" << std::endl;
#endif
}
Back to top page