Pagini recente » Cod sursa (job #355680) | Cod sursa (job #842983) | Cod sursa (job #1287415) | Cod sursa (job #2078185) | Cod sursa (job #1766494)
#include<fstream>
#define NMAX 100005
using namespace std;
int n, i, x, s[NMAX], y, leftPoz, h, sol, st, dr;
ifstream cin("xormax.in");
ofstream cout("xormax.out");
struct trie
{
trie *f[2];
int poz;
trie()
{
f[0] = f[1] = 0;
poz = 0;
}
};
trie *rad;
void insert_trie(trie *nod, int bit, int val, int poz)
{
if(bit == -1)
{
nod -> poz = poz;
return ;
}
if((val>>bit) & 1 == 1)
{
if(nod -> f[1] == NULL)
{
nod -> f[1] = new trie;
}
insert_trie(nod -> f[1], bit - 1, val, poz);
}else
{
if(nod -> f[0] == NULL)
{
nod -> f[0] = new trie;
}
insert_trie(nod -> f[0], bit - 1, val, poz);
}
}
void search_trie(trie *nod, int bit, int val)
{
if(bit == -1)
{
leftPoz= nod -> poz;
return ;
}
int searched_bit = 1 - (val>>bit) & 1;
if(nod -> f[searched_bit] == 0)
{
search_trie(nod -> f[1 - searched_bit], bit - 1, val);
}else
{
search_trie(nod -> f[searched_bit], bit - 1, val);
}
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> x;
s[i] = s[i - 1] ^ x;
y = max(y, s[i]);
}
while(y != 0)
{
y /= 2;
h++;
}
rad = new trie;
insert_trie(rad, h, 0, 0);
for(int i = 1; i <= n; i++)
{
search_trie(rad, h, s[i]);
if((s[i] ^ s[leftPoz]) > sol)
{
sol = s[i] ^ s[leftPoz]; st = leftPoz + 1; dr = i;
}
insert_trie(rad, h, s[i], i);
}
cout << sol << " " << st << " " << dr;
return 0;
}