Submission #1556160

---

Source Code Expand

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <functional>
#include <map>
#include <numeric>
#include <set>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(x) begin(x), end(x)
using namespace std;

int solve(int n, vector<int> const & a, vector<int> const & b) {
    if (a == b) {
        return 0;
    }
    int sum_a = accumulate(whole(a), 0, bit_xor<int>());
    {
        map<int, int> cnt;
        for (int a_i : a) {
            cnt[a_i] += 1;
        }
        cnt[sum_a] += 1;
        for (int b_i : b) {
            if (cnt.count(b_i)) {
                cnt[b_i] -= 1;
                if (cnt[b_i] == 0) {
                    cnt.erase(b_i);
                }
            }
        }
        assert (not cnt.empty());
        if (cnt.size() >= 2 or cnt.begin()->second >= 2) {
            return -1;  // impossible
        }
    }
    int mismatch = 0;
    repeat (i, n) {
        mismatch += (a[i] != b[i]);
    }
    int component = 0; {
        map<int, set<int> > g;
        repeat (i, n) {
            if (a[i] != b[i]) {
                g[b[i]].insert(a[i]);
            }
        }
        set<int> used;
        function<void (int)> go = [&](int a_i) {
            used.insert(a_i);
            for (int a_j : g[a_i]) if (not used.count(a_j)) {
                go(a_j);
            }
        };
        component += 1;
        if (g.count(sum_a)) {
            go(sum_a);
        }
        repeat (i, n) if (not used.count(a[i])) {
            if (g.count(a[i])) {
                component += 1;
                go(a[i]);
            }
        }
    }
    return mismatch + (component - 1);
}

int main() {
    int n; scanf("%d", &n);
    vector<int> a(n); repeat (i, n) scanf("%d", &a[i]);
    vector<int> b(n); repeat (i, n) scanf("%d", &b[i]);
    int result = solve(n, a, b);
    printf("%d\n", result);
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:70:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     int n; scanf("%d", &n);
                           ^
./Main.cpp:71:55: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     vector<int> a(n); repeat (i, n) scanf("%d", &a[i]);
                                                       ^
./Main.cpp:72:55: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     vector<int> b(n); repeat (i, n) scanf("%d", &b[i]);
                                                       ^

Judge Result