# Cod sursa(job #2026900)

Utilizator Data 25 septembrie 2017 12:15:14 Xor Max 0 cpp done Arhiva de probleme 1.75 kb
``````#include <fstream>

using namespace std;

ifstream in("xormax.in");
ofstream out("xormax.out");

const int NMax = 1000077;
int n, Start, End, Max = -1, sp[NMax];

struct trie
{
trie *z, *u;
int who;
trie()
{
z = NULL;
u = NULL;
who = 0;
}
}*Trie;

trie* insert(int i, int bit, trie *nod)
{
if(nod == NULL)
{
nod = new trie;
}
if(bit == -1)
{
nod->who = i;
return nod;
}

int fiu = sp[i] & (1<<bit);
if(fiu == 0)
{
nod->z = insert(i, bit - 1, nod->z);
}
else
{
nod->u=insert(i, bit - 1, nod->u);
}
}

int find(int val, int bit, trie *nod)
{
if (bit == -1)
{
return nod->who;
}

int fiu = val & (1<<bit);
if(fiu == 0)
{
if(nod->u != NULL)
{
return find(val, bit - 1, nod->u);
}
else
{
return find(val, bit - 1, nod->z);
}
}
else
{
if(nod->z != NULL)
{
return find(val, bit - 1, nod->z);
}
else
{
return find(val, bit - 1, nod->u);
}
}
}

int main()
{
int nr;
in >> n;
for(int i = 1; i <= n; ++i)
{
in >> nr;
in >> nr;
sp[i] = sp[i - 1] ^ nr;
}

Trie = insert(0, 21, Trie);
for(int i = 1; i <= n; ++i)
{
int Find = find(sp[i], 21, Trie);

if((sp[Find] ^ sp[i]) > Max)
{
Max = sp[Find] ^ sp[i];
Start = i;
End = Find + i;
}
Trie = insert(i, 21, Trie);
}

out << Max << " " << Start + 1 << " " << End + 1;

return 0;
}
``````