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/AtCoder/abc340_e.test.cpp

Depends on

Code

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

#include "../../Src/Template/IOSetting.hpp"
#include "../../Src/Algebra/Group/AdditiveGroup.hpp"
#include "../../Src/DataStructure/FenwickTree/DualFenwickTree.hpp"

/*
 * Atcoder Beginner Contest 340 - E Mancala 2
 * https://atcoder.jp/contests/abc340/submissions/63367056
 */

#include <iostream>
using namespace zawa;
int N, M, A[200020];
void solve() {
    SetFastIO();
    std::cin >> N >> M;
    for (int i = 0 ; i < N ; i++) std::cin >> A[i];
    DualFenwickTree<AdditiveGroup<long long>> fen{std::vector<long long>(A, A + N)};
    for (int i = 0 ; i < M ; i++) {
        int B;
        std::cin >> B;
        long long v = fen[B];
        fen.set(B, 0LL);
        {
            long long a = std::min<long long>(N - (B + 1), v);
            fen.operation(B + 1, B + 1 + a, 1);
            v -= a;
        }
        {
            long long a = v / N;
            if (a) fen.operation(0, N, a);
            v -= a * N;
        }
        {
            assert(v < N);
            fen.operation(0, v, 1);
        }
    }
    for (int i = 0 ; i < N ; i++) std::cout << fen[i] << (i + 1 == N ? '\n' : ' ');
}
int main() {
#ifdef ATCODER
    solve();
#else
    std::cout << "Hello World\n";
#endif
}
#line 1 "Test/AtCoder/abc340_e.test.cpp"
// #define PROBLEM "https://atcoder.jp/contests/abc340/tasks/abc340_e"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#line 2 "Src/Template/IOSetting.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/Template/IOSetting.hpp"

#include <iostream>
#include <iomanip>

namespace zawa {

void SetFastIO() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
}

void SetPrecision(u32 dig) {
    std::cout << std::fixed << std::setprecision(dig);
}

} // namespace zawa
#line 2 "Src/Algebra/Group/AdditiveGroup.hpp"

namespace zawa {

template <class T>
class AdditiveGroup {
public:
    using Element = T;
    static constexpr T identity() noexcept {
        return T{};
    }
    static constexpr T operation(const T& l, const T& r) noexcept {
        return l + r;
    }
    static constexpr T inverse(const T& v) noexcept {
        return -v;
    }
};

} // namespace zawa
#line 2 "Src/DataStructure/FenwickTree/DualFenwickTree.hpp"

#line 2 "Src/Algebra/Group/GroupConcept.hpp"

#line 2 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 2 "Src/Algebra/Semigroup/SemigroupConcept.hpp"

#include <concepts>

namespace zawa {

namespace concepts {

template <class T>
concept Semigroup = requires {
    typename T::Element;
    { T::operation(std::declval<typename T::Element>(), std::declval<typename T::Element>()) } -> std::same_as<typename T::Element>;
};

} // namespace concepts

} // namespace zawa
#line 4 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 6 "Src/Algebra/Monoid/MonoidConcept.hpp"

namespace zawa {

namespace concepts {

template <class T>
concept Identitiable = requires {
    typename T::Element;
    { T::identity() } -> std::same_as<typename T::Element>;
};

template <class T>
concept Monoid = Semigroup<T> and Identitiable<T>;

} // namespace

} // namespace zawa
#line 4 "Src/Algebra/Group/GroupConcept.hpp"

namespace zawa {

namespace concepts {

template <class T>
concept Inversible = requires {
    typename T::Element;
    { T::inverse(std::declval<typename T::Element>()) } -> std::same_as<typename T::Element>;
};

template <class T>
concept Group = Monoid<T> and Inversible<T>;

} // namespace Concept

} // namespace zawa
#line 5 "Src/DataStructure/FenwickTree/DualFenwickTree.hpp"

#include <bit>
#include <cassert>
#line 9 "Src/DataStructure/FenwickTree/DualFenwickTree.hpp"
#include <iterator>
#include <optional>
#include <vector>

namespace zawa {

namespace concepts {

template <class F, class V>
concept Predicate = requires {
    { std::declval<F>()(std::declval<V>()) } -> std::same_as<bool>; 
};

} // namespace Concept

template <concepts::Group G>
class DualFenwickTree {
public:

    using V = typename G::Element;

    constexpr static u32 Log2(usize n) noexcept {
        return static_cast<u32>(
                    std::bit_width(n) - (std::has_single_bit(n) ? 1 : 0)
                );
    }

    DualFenwickTree() = default;

    DualFenwickTree(usize n) : n_{n}, lg_{Log2(n)}, dat_(n+1, G::identity()) {
        assert(n);
    }

    DualFenwickTree(const std::vector<V>& d) : n_{d.size()}, lg_{Log2(n_)}, dat_(d.size() + 1, G::identity()) {
        assert(d.size());
        add(0, d[0]);
        for (usize i = 1 ; i < d.size() ; i++) add(i, G::operation(G::inverse(d[i - 1]), d[i]));
    }

    template <std::input_iterator It>
    DualFenwickTree(It first, It last) 
    : n_{static_cast<usize>(std::distance(first, last))}, lg_{Log2(n_)}, dat_(n_ + 1, G::identity()) {
        assert(first != last);
        V pv = static_cast<V>(*first);
        add(0, pv);
        for (usize i = 1 ; i < n_ ; i++) {
            first++;
            V v = static_cast<V>(*first);
            add(i, G::operation(G::inverse(pv), v));
            pv = v;
        } 
    }

    inline usize size() const noexcept {
        return n_;
    }

    void operation(usize l, usize r, const V& v) {
        assert(l <= r and r <= size());
        if (l < r) {
            add(l, v);
            if (r < size()) add(r, G::inverse(v));
        }
    }

    void operation(usize i, const V& v) {
        assert(i < size());
        operation(i, i + 1, v);
    }

    V operator[](i32 i) const {
        assert(0 <= i and i < (i32)size());
        V res = G::identity();
        for (i++ ; i ; i -= lsb(i)) res = G::operation(dat_[i], res);
        return res;
    }

    void set(usize i, V v) {
        assert(0 <= i and i < size());
        v = G::operation(G::inverse((*this)[i]), v);
        operation(i, v);
    }

    template <class F>
    std::optional<usize> maxRight(usize l, F f) const requires concepts::Predicate<F, V> {
        assert(l < size());
        V sum = l ? (*this)[l - 1] : G::identity();
        usize r = 0;
        for (u32 w = lg_ ; w <= lg_ ; w--) {
            usize next = r | (1u << w);
            if (next >= dat_.size()) continue;
            V nsum = G::operation(sum, dat_[next]);
            if (f(nsum)) {
                sum = std::move(nsum);
                r = std::move(next);
            }
        }
        assert(l <= r);
        return r == size() and f(sum) ? std::nullopt : std::optional{r};
    }

    // 実装が合いません。頭が悪いので
    // template <class F>
    // requires Concept::Predicate<F, V>
    // std::optional<usize> minLeft(usize r, F f) const {
    //     assert(r <= n_);
    //     V sum = G::identity();
    //     usize l = 0;
    //     for (u32 w = lg_ ; w <= lg_ ; w--) {
    //         u32 next = l | (1u << w);
    //         if (next >= r) continue;
    //         V nsum = G::operation(dat_[next], sum);
    //         if (!f(nsum)) {
    //             sum = std::move(nsum);
    //             l = std::move(next);
    //         }
    //     }
    //     assert(l <= r);
    //     if (l + 1 == r and !f(sum)) return r;
    //     return l == 0u and f(sum) ? std::nullopt : std::optional{l};
    // }

private:

    usize n_;

    u32 lg_;

    std::vector<V> dat_;

    constexpr i32 lsb(i32 x) const noexcept {
        return x & -x;
    }

    void add(i32 i, const V& v) {
        for (i++ ; i <= (i32)size() ; i += lsb(i)) dat_[i] = G::operation(dat_[i], v);
    }
};

} // namespace zawa
#line 7 "Test/AtCoder/abc340_e.test.cpp"

/*
 * Atcoder Beginner Contest 340 - E Mancala 2
 * https://atcoder.jp/contests/abc340/submissions/63367056
 */

#line 14 "Test/AtCoder/abc340_e.test.cpp"
using namespace zawa;
int N, M, A[200020];
void solve() {
    SetFastIO();
    std::cin >> N >> M;
    for (int i = 0 ; i < N ; i++) std::cin >> A[i];
    DualFenwickTree<AdditiveGroup<long long>> fen{std::vector<long long>(A, A + N)};
    for (int i = 0 ; i < M ; i++) {
        int B;
        std::cin >> B;
        long long v = fen[B];
        fen.set(B, 0LL);
        {
            long long a = std::min<long long>(N - (B + 1), v);
            fen.operation(B + 1, B + 1 + a, 1);
            v -= a;
        }
        {
            long long a = v / N;
            if (a) fen.operation(0, N, a);
            v -= a * N;
        }
        {
            assert(v < N);
            fen.operation(0, v, 1);
        }
    }
    for (int i = 0 ; i < N ; i++) std::cout << fen[i] << (i + 1 == N ? '\n' : ' ');
}
int main() {
#ifdef ATCODER
    solve();
#else
    std::cout << "Hello World\n";
#endif
}
Back to top page