Pagini recente » Cod sursa (job #638899) | Cod sursa (job #623713) | Cod sursa (job #304448) | Cod sursa (job #1907965) | Cod sursa (job #3347764)
#include <fstream>
using namespace std;
ifstream fin ("xormax.in");
ofstream fout ("xormax.out");
const int mxN = 100000 * 21 + 5;
int trie[mxN][2], nxt = 1, inx[mxN];
void add(long long a, int ind){
int nod = 1;
long long bit = 1 << 20;
for(int i = 0; i < 21; i++){
int v = (a & bit) ? 1 : 0;
if(!trie[nod][v]) trie[nod][v] = ++nxt;
nod = trie[nod][v];
bit = bit >> 1;
}
inx[nod] = ind;
}
long long xOrMax(long long a, int &ind){
int nod = 1;
long long bit = 1 << 20, ans = 0;
for(int i = 0; i < 21; i++){
int v = (a & bit) ? 1 : 0;
if(trie[nod][!v]) nod = trie[nod][!v], ans += bit;
else nod = trie[nod][v];
bit = bit >> 1;
}
ind = inx[nod];
return ans;
}
int main(){
int n, st, dr, indAux;
long long max = 0, aux = 0, x;
add(0, 0);
fin >> n;
for(int i = 1; i <= n; i++){
fin >> x;
aux = aux ^ x;
long long val = xOrMax(aux, indAux);
if(val >= max){
max = val;
st = indAux;
dr = i;
}
add(aux, i);
}
fout << max << " " << st + 1 << " " << dr;
}