Pagini recente » Cod sursa (job #364373) | Cod sursa (job #1843881) | Cod sursa (job #2567794) | Cod sursa (job #1341147) | Cod sursa (job #2159561)
#include <bits/stdc++.h>
using namespace std;
struct trie{
trie *f[2];
trie(){
memset(f, 0, sizeof(f));
}
};
int n, pr[100005], mx=-1, st, dr;
trie *rad = new trie;
unordered_map<int, int> m;
int main()
{
ifstream fin ("xormax.in");
ofstream fout ("xormax.out");
fin >> n;
trie *t = rad;
for (int i = 0; i < 20; ++i){
t->f[0] = new trie;
t = t->f[0];
}
m[0] = 0;
for (int i = 1; i <= n; ++i){
int x;
fin >> x;
pr[i] = pr[i-1]^x;
x = pr[i];
int pw = (1<<20);
t = rad;
while(pw){
int bit = 0;
if(x >= pw)
x -= pw, ++bit;
if(t->f[bit] == NULL)
t->f[bit] = new trie;
t = t->f[bit];
pw /= 2;
}
int sol = 0;
x = pr[i];
pw = (1<<20);
t = rad;
while(pw){
int bit = 0;
if(x >= pw)
x -= pw, ++bit;
if(t->f[1-bit] != NULL){
if(1-bit == 1)
sol += pw;
t = t->f[1-bit];
}else{
if(bit == 1)
sol += pw;
t = t->f[bit];
}
pw /= 2;
}
if((sol^pr[i]) > mx){
mx = sol^pr[i];
st = m[sol]+1;
dr = i;
}
m[pr[i]] = i;
}
fout << mx << " " << st << " " << dr << "\n";
return 0;
}