Submission #35998383

---

Source Code Expand

// #define MULTI_TESTCASES
// #define NDEBUG

// Utility
#include <algorithm>
#include <chrono>
#include <functional>
#include <iterator>
#include <limits>
#include <memory>
#include <numeric>
#include <random>
#include <type_traits>

// I/O
#include <fstream>
#include <iomanip>
#include <iostream>
#include <sstream>

// Data Structure
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <valarray>
#include <vector>

// Other Types
#include <complex>
#include <optional>
#include <tuple>
#include <utility>
#include <variant>

// C
#include <cassert>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

namespace kod {
namespace util {

template <class F> class FixedPoint : private F {
    constexpr FixedPoint(F&& f) : F(std::forward<F>(f)) {}
    template <class G> friend constexpr decltype(auto) fixed(G&&);

  public:
    template <class... Args> constexpr decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

template <class G> [[nodiscard]] constexpr decltype(auto) fixed(G&& g) {
    using F = std::decay_t<G>;
    return FixedPoint<F>(std::forward<F>(g));
}

}  // namespace util
}  // namespace kod

namespace kod {
namespace util {

struct Int1 {};
struct Chars {};

namespace io_impl {

template <class T> struct InputTypeImpl { using Type = T; };
template <> struct InputTypeImpl<Int1> { using Type = int; };
template <> struct InputTypeImpl<Chars> { using Type = std::vector<char>; };

template <class T> using InputType = typename InputTypeImpl<T>::Type;

}  // namespace io_impl

template <class T> io_impl::InputType<T> scan(std::istream& is) {
    T x;
    is >> x;
    return x;
}

template <> int scan<Int1>(std::istream& is) {
    int x;
    is >> x;
    return x - 1;
}

template <> std::vector<char> scan<Chars>(std::istream& is) {
    std::string s;
    is >> s;
    return std::vector<char>(std::cbegin(s), std::cend(s));
}

template <class T, int N> std::array<io_impl::InputType<T>, N> scan_arr(std::istream& is) {
    std::array<io_impl::InputType<T>, N> a;
    for (auto& x : a) x = scan<T>(is);
    return a;
}

template <class T> std::vector<io_impl::InputType<T>> scan_vec(std::istream& is, int n) {
    if (n == -1) n = scan<int>(is);
    assert(n >= 0);
    std::vector<io_impl::InputType<T>> v;
    v.reserve(n);
    while (n--) v.push_back(scan<T>(is));
    return v;
}

template <class T> io_impl::InputType<T> scan() {
    return scan<T>(std::cin);
}

template <class T, int N> std::array<io_impl::InputType<T>, N> scan_arr() {
    return scan_arr<T, N>(std::cin);
}

template <class T> std::vector<io_impl::InputType<T>> scan_vec(int n) {
    return scan_vec<T>(std::cin, n);
}

void print(std::ostream&) {}

template <class T, class... Args> void print(std::ostream& os, T&& x, Args&&... args) {
    os << x;
    if (sizeof...(args) != 0) os << ' ';
    print(os, std::forward<Args>(args)...);
}

template <class... Args> void println(std::ostream& os, Args&&... args) {
    print(os, std::forward<Args>(args)...);
    os << '\n';
}

template <class C>
void print_seq(std::ostream& os, C&& c, const char* sep = " ", const char* end = "\n") {
    bool f = false;
    for (auto&& x : c) {
        if (f) {
            os << sep;
        } else {
            f = true;
        }
        os << x;
    }
    os << end;
}

template <class... Args> void print(Args&&... args) {
    print(std::cout, std::forward<Args>(args)...);
}

template <class... Args> void println(Args&&... args) {
    println(std::cout, std::forward<Args>(args)...);
}

template <class C> void print_seq(C&& c, const char* sep = " ", const char* end = "\n") {
    print_seq(std::cout, std::forward<C>(c), sep, end);
}

}  // namespace util
}  // namespace kod

namespace kod {
namespace util {

class ForwardLoop {
    int src, dst;

    constexpr ForwardLoop(const int x, const int y) : src(x), dst(y) {}
    friend constexpr ForwardLoop rep(const int, const int);
    friend constexpr ForwardLoop rep(const int);

  public:
    constexpr ForwardLoop begin() const { return *this; }
    constexpr std::monostate end() const { return {}; }
    constexpr bool operator!=(std::monostate) const { return src < dst; }
    constexpr void operator++() const {}
    constexpr int operator*() { return src++; }
};

[[nodiscard]] constexpr ForwardLoop rep(const int l, const int r) {
    return ForwardLoop(l, r);
}
[[nodiscard]] constexpr ForwardLoop rep(const int n) {
    return ForwardLoop(0, n);
}

class BackwardLoop {
    int src, dst;

    constexpr BackwardLoop(const int x, const int y) : src(x), dst(y) {}
    friend constexpr BackwardLoop revrep(const int, const int);
    friend constexpr BackwardLoop revrep(const int);

  public:
    constexpr BackwardLoop begin() const { return *this; }
    constexpr std::monostate end() const { return {}; }
    constexpr bool operator!=(std::monostate) const { return src > dst; }
    constexpr void operator++() const {}
    constexpr int operator*() { return --src; }
};

[[nodiscard]] constexpr BackwardLoop revrep(const int l, const int r) {
    return BackwardLoop(r, l);
}
[[nodiscard]] constexpr BackwardLoop revrep(const int n) {
    return BackwardLoop(n, 0);
}

template <class F> constexpr void repeat(int n, const F& f) {
    assert(n >= 0);
    while (n--) f();
}

}  // namespace util
}  // namespace kod

namespace kod {
namespace util {

namespace nd_seq_impl {

template <class T, int N, std::enable_if_t<(N != 0)>* = nullptr> struct NdVectorImpl {
    using type = std::vector<typename NdVectorImpl<T, N - 1>::type>;
};
template <class T> struct NdVectorImpl<T, 1> { using type = std::vector<T>; };

template <class T, int N, int... Seq> struct NdArrayImpl {
    using type = std::array<typename NdArrayImpl<T, Seq...>::type, N>;
};
template <class T, int N> struct NdArrayImpl<T, N> { using type = std::array<T, N>; };

struct IsRangeImpl {
    template <class T>
    static auto check(T&& obj) -> decltype(std::begin(obj), std::end(obj), std::true_type{});
    template <class T> static auto check(...) -> std::false_type;
};

template <class T>
constexpr bool is_range_v = decltype(IsRangeImpl::check<T>(std::declval<T>()))::value;
template <class T>
constexpr bool has_range_v =
    is_range_v<T>&& is_range_v<decltype(*std::begin(std::declval<T>()))>;

}  // namespace nd_seq_impl

template <class T, int N> using NdVector = typename nd_seq_impl::NdVectorImpl<T, N>::type;

template <class T> decltype(auto) nd_vec(const int size, T&& value) {
    using U = std::decay_t<T>;
    return std::vector<U>(size, std::forward<U>(value));
}

template <class... Args> decltype(auto) nd_vec(const int size, Args&&... args) {
    assert(size >= 0);
    return std::vector<decltype(nd_vec(std::forward<Args>(args)...))>(
        size, nd_vec(std::forward<Args>(args)...));
}

template <class T, int N, int... Seq>
using NdArray = typename nd_seq_impl::NdArrayImpl<T, N, Seq...>::type;

template <class R, class T, std::enable_if_t<nd_seq_impl::has_range_v<R>>* = nullptr>
constexpr void fill(R&& range, T&& value) {
    for (auto&& e : range) fill(std::forward<decltype(e)>(e), std::forward<T>(value));
}
template <class R, class T, std::enable_if_t<!nd_seq_impl::has_range_v<R>>* = nullptr>
constexpr void fill(R&& range, T&& value) {
    std::fill(std::begin(range), std::end(range), std::forward<T>(value));
}

}  // namespace util
}  // namespace kod

namespace kod {
namespace sol {

template <class T> constexpr bool setmin(T& lhs, const T& rhs) {
    if (lhs > rhs) {
        lhs = rhs;
        return true;
    }
    return false;
}
template <class T> constexpr bool setmax(T& lhs, const T& rhs) {
    if (lhs < rhs) {
        lhs = rhs;
        return true;
    }
    return false;
}

template <class T, std::enable_if_t<std::is_integral_v<T>>* = nullptr>
constexpr T infty = std::numeric_limits<T>::max() / 2;

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;

using std::array;
using std::pair;
using std::tuple;
using std::vector;

using namespace util;

void run();

}  // namespace sol
}  // namespace kod

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(20);
    std::cerr << std::unitbuf;
    int cases = 1;
#ifdef MULTI_TESTCASES
    std::cin >> cases;
#endif
    while (cases--) kod::sol::run();
    return 0;
}

namespace kod {
namespace sol {

void run() {
    const int n = scan<int>();
    const auto a = scan_vec<int>(n);
    const auto b = scan_vec<int>(n);
    vector<array<int, 4>> node = {{-1, -1, -1, 0}};
    const auto add = [&](int x) {
        vector<int> v;
        while (x > 0) {
            v.push_back(x);
            x /= 2;
        }
        std::reverse(v.begin(), v.end());
        int n = 0, a = 0;
        for (const int b : v) {
            const int k = b - 2 * a;
            if (node[n][k] == -1) {
                node[n][k] = node.size();
                node.push_back({-1, -1, n, 0});
            }
            n = node[n][k];
            a = b;
        }
        return n;
    };
    for (const int x : a) {
        node[add(x)][3] += 1;
    }
    for (const int x : b) {
        node[add(x)][3] -= 1;
    }
    int ans = 0;
    const bool can = fixed([&](auto&& dfs, const int u) -> bool {
        const int l = node[u][0];
        const int r = node[u][1];
        if (l != -1) {
            if (!dfs(l)) return false;
            ans += std::abs(node[l][3]);
            node[u][3] += node[l][3];
        }
        if (r != -1) {
            if (!(dfs(r)) or node[r][3] < 0) return false;
            ans += node[r][3];
            node[u][3] += node[r][3];
        }
        return true;
    })(0);
    println(can ? ans : -1);
}

}  // namespace sol
}  // namespace kod

Submission Info

Judge Result