# Cod sursa(job #429683)

Utilizator Data 30 martie 2010 13:06:12 Xor Max 100 cpp done Arhiva de probleme 1.34 kb
``````#include <fstream>

#define NMAX 100100
#define BMAX 23
using namespace std;

struct Trie
{
int L;
Trie* f[2];

Trie()
{
f[0] = f[1] = 0;
L = 0;
}
};
Trie* T;

int N, A[NMAX], best, bestI, bestJ, Sum[NMAX], j;

void readAll(void)
{
ifstream fin("xormax.in");

fin >>N;

for (int i = 1; i <= N; i++)
fin >>A[i];

fin.close();
}

void Cauta(Trie* T, int B, int Nr)
{
if (!T->f[0] && !T->f[1] ) {j = T->L; return;}

int x = 0;
if ( (1 << B) & Nr ) x = 1;

if ( T->f[1-x] ) Cauta(T->f[1-x], B-1, Nr);
else Cauta(T->f[x], B-1, Nr);
}

void Add(Trie* T, int B, int Nr, int Ind)
{
int x = 0;
if ( (1 << B) & Nr ) x = 1;

if (!T->f[x]) T->f[x] = new Trie;

if (B == 0) T->f[x]->L = Ind;
else Add(T->f[x], B - 1, Nr, Ind);
}

void Solve(void)
{
int i;

T = new Trie;

best = Sum[1];
bestI = 1;
bestJ = 0;
Add(T, BMAX, 0, 0);

for (i = 1; i <= N; i++)
{
Sum[i] = Sum[i-1] ^ A[i];

Cauta(T, BMAX, Sum[i]);

if ( (Sum[i] ^ Sum[j]) > best)
{
best = Sum[i] ^ Sum[j];
bestI = i;
bestJ = j;
}
Add(T, BMAX, Sum[i], i);
}
}

void writeAll(void)
{
ofstream fout("xormax.out");

fout <<best <<' '<<bestJ + 1 <<' '<<bestI <<'\n';

fout.close();
}

int main()
{
readAll();

Solve();

writeAll();

return 0;
}
``````