Pagini recente » Cod sursa (job #2312257) | Cod sursa (job #2081477) | Cod sursa (job #145377) | Cod sursa (job #2269647) | Cod sursa (job #1491984)
#include <fstream>
using namespace std;
#define pii pair<int,int>
#define mp make_pair
#define position first
#define value second
#define BITS 21
struct trie
{
int poz;
trie* fiu[2];
trie()
{
poz = -1;
fiu[0] = fiu[1] = NULL;
}
} *rad;
void insert(int, int) ;
pii getPos(int) ;
int main()
{
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int i, n, a, sxor;
int rez, start, stop;
pii aux;
rad = new trie;
insert(0, 0);
fin >> n;
for(rez = -1, sxor = 0, i = 1; i <= n; ++i)
{
fin >> a;
sxor ^= a;
aux = getPos(sxor);
if((aux.value ^ sxor) > rez)
{
rez = aux.value ^ sxor;
start = aux.position + 1;
stop = i;
}
insert(i, sxor);
}
fout << rez << ' ' << start << ' ' << stop << '\n';
return 0;
}
void insert(int p, int val)
{
int k, bit;
trie* nod;
for(nod = rad, k = BITS; k >= 0; --k)
{
bit = ((val & (1 << k)) != 0);
if(nod -> fiu[bit] == NULL)
nod -> fiu[bit] = new trie;
nod = nod -> fiu[bit];
}
if(nod -> poz == -1) nod -> poz = p;
}
pii getPos(int val)
{
int k, bit, rez;
trie* nod;
for(nod = rad, rez = 0, k = BITS; k >= 0; --k)
{
bit = ((val & (1 << k)) == 0);
if(nod -> fiu[bit] == NULL) bit = !bit;
if(bit) rez |= (1 << k);
nod = nod -> fiu[bit];
}
return mp(nod -> poz, rez);
}