// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/set_xor_min #include #include #include #include #include #include /// @brief 座標圧縮 template struct coordinate_compression { coordinate_compression() = default; coordinate_compression(const std::vector &_data) : data(_data) { build(); } const T &operator[](int i) const { return data[i]; } void add(T x) { data.emplace_back(x); } void build() { std::sort(data.begin(), data.end()); data.erase(std::unique(data.begin(), data.end()), data.end()); } bool exists(T x) const { auto it = std::lower_bound(data.begin(), data.end(), x); return it != data.end() && *it == x; } int get(T x) const { return std::distance(data.begin(), std::lower_bound(data.begin(), data.end(), x)); } int lower_bound(T x) const { return std::distance(data.begin(), std::lower_bound(data.begin(), data.end(), x)); } int upper_bound(T x) const { return std::distance(data.begin(), std::upper_bound(data.begin(), data.end(), x)); } std::vector compress(const std::vector &v) const { int n = v.size(); std::vector res(n); for (int i = 0; i < n; ++i) res[i] = get(v[i]); return res; } int size() const { return data.size(); } private: std::vector data; }; /// @brief 座標圧縮 template std::vector compress(const std::vector &v) { coordinate_compression cps(v); std::vector res; res.reserve(std::size(v)); for (auto &&x : v) res.emplace_back(cps.get(x)); return res; } #include /** * @brief フェニック木 * @see http://hos.ac/slides/20140319_bit.pdf * * @tparam T */ template struct fenwick_tree { fenwick_tree() : _size(), data() {} fenwick_tree(int n) : _size(n + 1), data(n + 1) {} template fenwick_tree(const std::vector &v) : _size((int)v.size() + 1), data((int)v.size() + 1) { build(v); } T operator[](int i) const { return sum(i, i + 1); } T at(int k) const { return operator[](k); } T get(int k) const { return operator[](k); } template void build(const std::vector &v) { for (int i = 0, n = v.size(); i < n; ++i) data[i + 1] = v[i]; for (int i = 1; i < _size; ++i) { if (i + (i & -i) < _size) data[i + (i & -i)] += data[i]; } } void set(int k, T val) { add(k, val - at(k)); } void update(int k, T val) { set(k); } void add(int k, T val) { assert(0 <= k && k < _size - 1); for (++k; k < _size; k += k & -k) data[k] += val; } bool chmax(int k, T val) { if (at(k) >= val) return false; set(k, val); return true; } bool chmin(int k, T val) { if (at(k) <= val) return false; set(k, val); return true; } T all_prod() const { return prod(_size - 1); } T prod(int k) const { return sum(k); } T prod(int a, int b) const { return sum(a, b); } T all_sum() const { return sum(_size - 1); } T sum(int k) const { assert(0 <= k && k < _size); T res = 0; for (; k > 0; k -= k & -k) res += data[k]; return res; } T sum(int a, int b) const { assert(0 <= a && a <= b && b < _size); T res = T(); while (a != b) { if (a < b) { res += data[b]; b -= b & -b; } else { res -= data[a]; a -= a & -a; } } return res; } int lower_bound(T val) const { if (val <= 0) return 0; int k = 1; while (k < _size) k <<= 1; int res = 0; for (; k > 0; k >>= 1) { if (res + k < _size && data[res + k] < val) val -= data[res += k]; } return res; } private: int _size; std::vector data; }; /// @brief 転倒数 template std::int64_t inversion_number(const std::vector &v) { if (v.empty()) return 0; auto u = compress(v); std::reverse(u.begin(), u.end()); fenwick_tree bit(*std::max_element(u.begin(), u.end()) + 1); std::int64_t res = 0; for (auto x : u) { res += bit.sum(x); bit.add(x, 1); } return res; } /// @brief 転倒数 template std::int64_t inversion_number_of_permutation(const std::vector &v) { if (v.empty()) return 0; int n = v.size(); fenwick_tree bit(n); std::int64_t res = 0; for (int i = n - 1; i >= 0; --i) { res += bit.sum(v[i]); bit.add(v[i], 1); } return res; } /// @brief 最小隣接スワップ回数 template std::int64_t swap_distance(const std::vector &a, const std::vector &b) { // verify : https://atcoder.jp/contests/arc120/tasks/arc120_c if (a.size() != b.size()) return -1; int n = a.size(); std::vector c(n), d(n); std::iota(c.begin(), c.end(), 0); std::iota(d.begin(), d.end(), 0); std::stable_sort(c.begin(), c.end(), [&a](int x, int y) { return a[x] < a[y]; }); std::stable_sort(d.begin(), d.end(), [&b](int x, int y) { return b[x] < b[y]; }); std::vector p(n); for (int i = 0; i < n; ++i) { int x = c[i], y = d[i]; if (a[x] != b[y]) return -1; p[x] = y; } return inversion_number_of_permutation(p); } int main(void) { int n; std::cin >> n; std::vector a(n), b(n); for (auto &e : a) std::cin >> e; for (auto &e : b) std::cin >> e; if (a[0] != b[0]) { std::cout << -1 << '\n'; return 0; } std::vector c(n - 1), d(n - 1); for (int i = 0; i < n - 1; ++i) { c[i] = a[i] ^ a[i + 1]; d[i] = b[i] ^ b[i + 1]; } std::cout << swap_distance(c, d) << '\n'; return 0; }