Submission #1365639

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
struct UnionFind { vector<int> par,cnt;
    UnionFind(int NV){par.clear();cnt.resize(NV, 1);rep(i, 0, NV) par.push_back(i); } 
    int operator[](int x) { return par[x] == x ? x : par[x] = operator[](par[x]); }
    void operator()(int x, int y) { x = operator[](x); y = operator[](y);
        if (x != y) par[x] = y, cnt[y] += cnt[x]; }};
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/




int N, A[101010], B[101010];
//---------------------------------------------------------------------------------------------------
bool chk() {
    map<int, int> cnt;
    rep(i, 0, N + 1) cnt[A[i]]++;
    rep(i, 0, N + 1) { if (cnt[B[i]] == 0) return false; cnt[B[i]]--; }
    return true;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cin >> B[i];

    A[N] = 0;
    rep(i, 0, N) A[N] ^= A[i];

    B[N] = 0;
    rep(i, 0, N) B[N] ^= B[i];

    if (!chk()) { printf("-1\n"); return; }

    int e = 0, c = 0, d = 0;

    if (A[N] != B[N]) {
        e++;
        rep(i, 0, N) if (A[i] != B[i] && B[i] == A[N]) {
            swap(A[i], A[N]);
            break;
        }
    }

    vector<int> dic;
    rep(i, 0, N) if (A[i] != B[i]) {
        c++;
        dic.push_back(A[i]);
    }
    sort(dic.begin(), dic.end());
    dic.erase(unique(dic.begin(), dic.end()), dic.end());

    UnionFind uf(dic.size());
    rep(i, 0, N + 1) if (A[i] != B[i]) {
        int a = lower_bound(dic.begin(), dic.end(), A[i]) - dic.begin();
        int b = lower_bound(dic.begin(), dic.end(), B[i]) - dic.begin();
        uf(a, b);
    }

    rep(i, 0, dic.size()) if (uf[i] == i) c++;

    rep(i, 0, N) if (A[i] != B[i] && B[i] == A[N]) {
        d = -1;
        break;
    }

    int ans = e + c + d;
    cout << ans << endl;
}

Submission Info

Judge Result