Let cnt1a be the the number of elements in A where the i-th bit is 1, cnt0a be the the number of elements in A where the i-th bit is 0. cnt1b and cnt0b are defined in the same way but for the set B. If cnt1a==cnt0b => the i-th bit in x is 1, else if cnt1a==cnt1b => the i-th bit in x is 0, else such x doesn't exist. Also in the end you have to check that x transforms set A to set B, which you can do easily with sets.

I think the problem can be reduced to the following two:

1. Given two sets A and B, find X such that .
2. Given a set S, find all d such that .

Can you provide a link to the problem?

Please send halp anyone

I'm don't check this but seems right. Look at the basis of A (name it B_a) and basis of B (name it B_b). Any of them has at most log vectors. We need to map one onto another one. If we fix image in B_b of any arbitrary vector from B_a we will now have image off whole A and we may check if latter equals B in O(nlogn) or better. Only log different images we may choose for our vector from A thus smth like O(nlog²n) we have.

The problem is a tough one(solved by only one). You can always ask your friend who has coach rights. Judge Solution — http://ideone.com/GQJJBU

First contract the multimaps as (number,occurrences) then if the occurrences multimaps are not equal then there can't be a solution since X will map each different number to different number. Then create a candidate of solutions and try them all(random_shuffle and time cutoff seems to be the trick emplyed here).

I just don't understand...What's the problem with solving the problem for each bit independently?

Ok, since my last explanation was very confusing, I'll try explaining it again more clearly, also with code. We itterate on each bit i. We count how many elements in A have the bit i equal to 0 (We store this count in cnt0a), how many have it equal to 1 (store in cnt1a) and the same for B (store in cnt0b and cnt1b)

for(int i=0;i<63;i++){
    for(int j=1;j<=n;j++){
        (!(a[j] & (1 << i))) cnt0a++;
        else cnt1a++;
        (!(b[j] & (1 << i))) cnt0b++;
        else cnt1b++;
    }
}

Obviously cnt0a+cnt1a=cnt0b+cnt1b=63;

Now let's assume that a solution X exists. For every bit i we must have either cnt0a==cnt1b (and obiously then cnt1a==cnt0b) (Then the i-th bit of X is 1, and transforms all 0s into 1s and viceversa), or cnt0a==cnt0b (and obiously then cnt1a==cnt1b) (Then the i-th bit of X is 0, and transforms all 0s into 0s and all 1s into 1s). Otherwise, no X exists. Then we can tell the i-th bit of X for all bits, EXCEPT for the case that cnt0a==cnt1a, then we can't tell what the i-th bit of X is. We set this bit as unknown. Let's ignore the unknown bits for now.

for(int i=0;i<63;i++){
    for(int j=1;j<=n;j++){
        if(!(a[j] & (1 << i))) cnt0a++;
        else cnt1a++;
        if(!(b[j] & (1 << i))) cnt0b++;
        else cnt1b++;
        if(cnt0a==cnt1b) unknown[i]=1;
        else{
            if(cnt0a==cnt1b) x+=(1<<i);
            else if(cnt0a==cnt0b);
            else{
                cout << "-1";
                return 0;
            }
        }
    }
}

Next step is to find the unknown bits. Lets create two sets C and D, which contain all elemnts in A and B respectively, but with the known bits equal bits missing (or all equal to 0 for an easier code, its equivallent).

for(int i=0;i<63;i++){
    if(!unknown[i]) continue;
    for(int j=1;j<=n;j++){
        if(!(a[j] & (1 << i))) c[j]+=(1<<i);
        if(!(b[j] & (1 << i))) d[j]+=(1<<i);
    }
}

We have the following in sets C and D: cnt1a==cnt0a==cnt1b==cnt0b for every bit i, since it only contains unknown bits, which have this property, or only 0s.

Again, we assumed such an X exists. Then let's prove that X=C[1]^D[1], or any C[i]^D[j] for that matter. Let Y=C[1]^D[1]. Lets remove C[1] and D[1] for the sets entirely. Let's find X for this remaining set of n-1 elements.

Now, for each bit i, we have two cases: 1. We removes two 1s or two 0s => the i-th bit of Y is 0, cnt1a!=cnt0a, cnt1a==cnt1b, cnt0a==cnt0b. Thus, with the same reasoning as previously, the i-th bit of X is 0, and it coincides with the i-th bit of Y. 2. We removes one 1 and one 0 => the i-th bit of Y is 1, cnt1a!=cnt0a, cnt1a==cnt0b, cnt0a==cnt1b. Thus, with the same reasoning as previously, the i-th bit of X is 1, and it coincides with the i-th bit of Y.

Thus X==Y, so it works for the deleted elements too. Thus the X for sets C and D is just C[1]^D[1]. Of course, this ONLY works if there exists a valid solution for X.

Now we just sum the two Xs we've got to get the final answer.

x+=c[1]^d[1];

Observe that all we've done so far was right, but we assumed that a solution X exists! What if it doesnt? Well the X we've found is the only possible X, but it might be wrong. We have to check it. It can easily be done using multisets.

for(int i=1;i<=n;i++) s.insert(b[i]);
for(int i=1;i<=n;i++){
    a[i]^=x;
    auto it=s.find(a[i]);
    if(it==s.end()){
        cout << -1;
        return 0;
    }
    s.erase(it);
}
cout << x;

I hope it was clear, if you have any questions or if I am wrong somehow please let me know.

where is its judge?

1) The answer can be broken down independently to each bit. 2) Having reduced the problem to one bit, you can easily see that the answer can be zero or one, or both (when the elements that are 1 equal the ones that are 0).

What about putting all elements of A (with multiplicity) in a binary trie, do the same with elements of B and then doing tree isomorphism?