Pagini recente » Cod sursa (job #520978) | Cod sursa (job #931252) | Cod sursa (job #222913) | Cod sursa (job #1135039) | Cod sursa (job #2026900)
#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;
}