Pagini recente » Cod sursa (job #2717405) | Cod sursa (job #745421) | Cod sursa (job #697910) | Cod sursa (job #2904275) | Cod sursa (job #519701)
Cod sursa(job #519701)
#include <iostream>
#include <string>
using namespace std;
#define TM 1000005
#define NM 100005
int trie[TM][2], C[TM], noduri;
int A[NM], op, pop;
int insereaza (int numar, int poz)
{
int p = 20;
int nod = 0, digit;
while (p >= 0)
{
if ((1<<p) & numar) digit = 1;
else digit = 0;
if (!trie[nod][digit])
{
++noduri;
trie[nod][digit] = noduri;
}
nod = trie[nod][digit];
--p;
}
C[nod] = poz;
}
void cauta (int numar)
{
op = 0;
int p = 20;
int nod = 0, digit;
while (p >= 0)
{
if ((1<<p) & numar) digit = 0;
else digit = 1;
if (trie[nod][digit])
{
op += digit * (1<<p);
nod = trie[nod][digit];
}
else
{
op += (1-digit) * (1<<p);
nod = trie[nod][1-digit];
}
--p;
}
pop = C[nod];
}
int main()
{
int best = -1, st, dr, N;
freopen ("xormax.in", "r", stdin);
freopen ("xormax.out", "w", stdout);
scanf ("%d", &N);
for (int i = 1; i <= N; ++i) scanf ("%d", &A[i]);
int sum_xor = 0;
insereaza (sum_xor, 0);
for (int i = 1; i <= N; ++i)
{
sum_xor = sum_xor ^ A[i];
cauta (sum_xor);
insereaza (sum_xor, i);
if ((op^sum_xor) > best)
{
best = op^sum_xor;
dr = i;
st = pop + 1;
}
//printf ("%d ", op^sum_xor);
}
//printf ("\n");
printf ("%d %d %d", best, st, dr);
return 0;
}