Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Try tracking how every remaining element changes together. The operation XORs the same value into all survivors, so maybe the whole array has one shared “mask” slapped onto the original values.
After some operations, suppose every remaining original element currently looks like . What happens if you choose the element whose original value was ?
The chosen value is . After XORing every survivor by , the new shared mask becomes That cancellation is the whole damn trick.
So after each operation, the shared mask is just the original value of the element removed most recently. Therefore the final survivor ends as , where was removed right before it.
Any two distinct indices can be made the last two indices: remove everyone else first, remove one of them second-to-last, and keep the other. So the answer is simply
Label each element by its original value. At any moment, every remaining element has the form
for one shared mask .
Initially, , so this is obviously true. Now suppose we remove the element whose original value is . Its current value is
The operation XORs into every element. So every survivor changes from
to
That means the new shared mask is
Boom. After an operation, the shared mask becomes exactly the original value of the element just removed. All previous history gets nuked by XOR cancellation. Very polite of the problem, honestly.
Let the removal order be
and let be the final remaining index.
After the last removal, the shared mask is the original value of the second-to-last element removed:
So the final remaining value is
The earlier removed elements do not matter at all. They were dramatic extras.
Any two distinct indices and can be made the last two:
Then the final value is
Therefore the set of possible answers is exactly
So we just compute
The total over all test cases is at most , so brute forcing all pairs is completely fine:
time per test case and
extra memory besides the array.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
ans = max(ans, a[i] ^ a[j]);
}
}
cout << ans << '\n';
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
ans = max(ans, a[i] ^ a[j]);
}
}
cout << ans << '\n';
}
return 0;
}