Pagini recente » Cod sursa (job #1026581) | Cod sursa (job #2570288) | Cod sursa (job #1573658) | Cod sursa (job #1249973) | Cod sursa (job #3354387)
#include <bits/stdc++.h>
using namespace std;
int main() {
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n, u = 1;
vector<int> prefix_xor(n + 1, 0);
vector<int> tree(1 << 22, -1);
for (int i = 20; i >= 0; i--){
u = 2 * u;
tree[u] = 0;
}
int max_xor = -1;
int best_start = -1, best_stop = -1;
for(int i = 1; i <= n; i++){
int val;
fin >> val;
prefix_xor[i] = prefix_xor[i - 1] ^ val;
int current_pref = prefix_xor[i];
u = 1;
for(int bit_pos = 20; bit_pos >= 0; bit_pos--){
int bit = (current_pref >> bit_pos) & 1;
int opposite = 1 - bit;
if(tree[2 * u + opposite] != -1)
u = 2 * u + opposite;
else u = 2 * u + bit;
}
int j = tree[u];
int temp_xor = current_pref ^ prefix_xor[j];
if(temp_xor > max_xor){
max_xor = temp_xor;
best_start = j + 1;
best_stop = i;
}
u = 1;
for(int bit_pos = 20; bit_pos >= 0; bit_pos--){
int bit = (current_pref >> bit_pos) & 1;
u = 2 * u + bit;
tree[u] = i;
}
}
fout<<max_xor<<" "<<best_start<<" "<<best_stop<<"\n";
return 0;
}