Pagini recente » Cod sursa (job #2247314) | Cod sursa (job #597788) | Cod sursa (job #836223) | Cod sursa (job #497772) | Cod sursa (job #3149671)
#include <bits/stdc++.h>
using namespace std;
const int LMAX = 31;
const int NMAX = 1e5+2;
int n,x,pref[NMAX];
ifstream fin("xormax.in");
ofstream fout("xormax.out");
struct BitTrie{
int idx = 0;
BitTrie * children[2] = {nullptr};
} root;
void add(int x, int id){
BitTrie * ptr = &root;
for(int i = LMAX; i >= 0; i--){
int bit = (x>>i)&1;
if(ptr->children[bit] == nullptr){
BitTrie * new_branch = new BitTrie;
ptr->children[bit] = new_branch;
ptr = new_branch;
}else{
ptr = ptr->children[bit];
}
}
ptr->idx = id;
}
int get_best_approx(int x){
BitTrie * ptr = &root;
for(int i = LMAX; i >= 0; i--){
int bit = (x>>i)&1;
if(ptr->children[bit] != nullptr){
ptr = ptr->children[bit];
}else{
ptr = ptr->children[!bit];
}
}
return ptr->idx;
}
int main()
{
fin >> n;
int maxi = 0, l = 0, r = 0;
int lenmin = n;
add(0, 0);
for(int i = 1; i <= n; i++){
fin >> x;
pref[i] = pref[i-1]^x;
int ind = get_best_approx(~pref[i]);
int val = pref[i]^pref[ind];
if(val > maxi){
maxi = val;
l = ind+1, r = i;
}else if(val == maxi){
int len = i-(ind+1)-1;
if(lenmin > len){
l = ind+1, r = i;
}
}
add(pref[i], i);
}
fout << maxi << " " << l << " " << r;
return 0;
}