結果

問題 No.1209 XOR Into You
ユーザー kuhaku
提出日時 2025-05-23 17:55:47
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 140 ms / 2,000 ms
コード長 5,592 bytes
コンパイル時間 1,628 ms
コンパイル使用メモリ 122,100 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-05-23 17:55:54
合計ジャッジ時間 7,573 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/set_xor_min
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdint>
#include <numeric>
#include <iterator>
/// @brief 座標圧縮
template <class T>
struct coordinate_compression {
    coordinate_compression() = default;
    coordinate_compression(const std::vector<T> &_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<int> compress(const std::vector<T> &v) const {
        int n = v.size();
        std::vector<int> 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<T> data;
};
/// @brief 座標圧縮
template <class T>
std::vector<int> compress(const std::vector<T> &v) {
    coordinate_compression cps(v);
    std::vector<int> res;
    res.reserve(std::size(v));
    for (auto &&x : v) res.emplace_back(cps.get(x));
    return res;
}
#include <cassert>
/**
 * @brief フェニック木
 * @see http://hos.ac/slides/20140319_bit.pdf
 *
 * @tparam T
 */
template <class T>
struct fenwick_tree {
    fenwick_tree() : _size(), data() {}
    fenwick_tree(int n) : _size(n + 1), data(n + 1) {}
    template <class U>
    fenwick_tree(const std::vector<U> &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 <class U>
    void build(const std::vector<U> &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<T> data;
};
/// @brief 転倒数
template <class T>
std::int64_t inversion_number(const std::vector<T> &v) {
    if (v.empty()) return 0;
    auto u = compress(v);
    std::reverse(u.begin(), u.end());
    fenwick_tree<T> 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 <class T>
std::int64_t swap_distance(const std::vector<T> &a, const std::vector<T> &b) {
    // verify : https://atcoder.jp/contests/arc120/tasks/arc120_c
    if (a.size() != b.size()) return -1;
    int n = a.size();
    std::vector<int> 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<int> 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(p);
}
int main(void) {
    int n;
    std::cin >> n;
    std::vector<int> 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<int> 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;
}
0