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

Depends on

Code

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

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

/*
 * AtCoder Regular Contest 088 - E Papple Sort
 * https://atcoder.jp/contests/arc088/submissions/63367117
 */

#include <algorithm>
#include <iostream>
#include <string>
#include <numeric>
using namespace zawa;
std::string S;
std::vector<int> pos[26];
std::vector<std::pair<int, int>> match[26];
bool is_palin() {
    int odd = 0;
    for (int i = 0 ; i < 26 ; i++) odd += pos[i].size() & 1;
    return odd <= 1;
}
int main() {
#ifdef ATCODER
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cin >> S;
    for (int i = 0 ; i < (int)S.size() ; i++) pos[S[i] - 'a'].push_back(i);
    if (is_palin()) {
        for (int i = 0 ; i < 26 ; i++) {
            match[i].reserve(pos[i].size() / 2);
            for (int j = 0, k = (int)pos[i].size() - 1 ; j < k ; j++, k--) {
                match[i].push_back({ pos[i][j], pos[i][k] });
            }
            std::reverse(match[i].begin(), match[i].end());
        }
        std::vector<int> init(S.size());
        std::iota(init.begin(), init.end(), 0);
        DualFenwickTree<AdditiveGroup<int>> fen{init};
        long long ans = 0;
        for (int l = 0, r = (int)S.size() - 1 ; l < r ; l++, r--) {
            int min = (int)1e9, arg = -1;
            for (int i = 0 ; i < 26 ; i++) if (match[i].size()) {
                auto [ll, rr] = match[i].back();
                int cost = fen[ll] - l + r - fen[rr];
                if (min > cost) {
                    min = cost;
                    arg = i;
                }
            }
            assert(arg != -1);
            auto [ll, rr] = match[arg].back();
            match[arg].pop_back();
            ans += min;
            fen.operation(0, ll, 1);
            fen.operation(rr + 1, S.size(), -1);
        }
        std::cout << ans << '\n';
    }
    else {
        std::cout << -1 << '\n';
    }
#else
    std::cout << "Hello World\n";
#endif
}
#line 1 "Test/AtCoder/arc088_e.test.cpp"
// #define PROBLEM "https://atcoder.jp/contests/arc088/tasks/arc088_c"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#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/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 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 6 "Test/AtCoder/arc088_e.test.cpp"

/*
 * AtCoder Regular Contest 088 - E Papple Sort
 * https://atcoder.jp/contests/arc088/submissions/63367117
 */

#include <algorithm>
#include <iostream>
#include <string>
#include <numeric>
using namespace zawa;
std::string S;
std::vector<int> pos[26];
std::vector<std::pair<int, int>> match[26];
bool is_palin() {
    int odd = 0;
    for (int i = 0 ; i < 26 ; i++) odd += pos[i].size() & 1;
    return odd <= 1;
}
int main() {
#ifdef ATCODER
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cin >> S;
    for (int i = 0 ; i < (int)S.size() ; i++) pos[S[i] - 'a'].push_back(i);
    if (is_palin()) {
        for (int i = 0 ; i < 26 ; i++) {
            match[i].reserve(pos[i].size() / 2);
            for (int j = 0, k = (int)pos[i].size() - 1 ; j < k ; j++, k--) {
                match[i].push_back({ pos[i][j], pos[i][k] });
            }
            std::reverse(match[i].begin(), match[i].end());
        }
        std::vector<int> init(S.size());
        std::iota(init.begin(), init.end(), 0);
        DualFenwickTree<AdditiveGroup<int>> fen{init};
        long long ans = 0;
        for (int l = 0, r = (int)S.size() - 1 ; l < r ; l++, r--) {
            int min = (int)1e9, arg = -1;
            for (int i = 0 ; i < 26 ; i++) if (match[i].size()) {
                auto [ll, rr] = match[i].back();
                int cost = fen[ll] - l + r - fen[rr];
                if (min > cost) {
                    min = cost;
                    arg = i;
                }
            }
            assert(arg != -1);
            auto [ll, rr] = match[arg].back();
            match[arg].pop_back();
            ans += min;
            fen.operation(0, ll, 1);
            fen.operation(rr + 1, S.size(), -1);
        }
        std::cout << ans << '\n';
    }
    else {
        std::cout << -1 << '\n';
    }
#else
    std::cout << "Hello World\n";
#endif
}
Back to top page