Pagini recente » Cod sursa (job #2946408) | Cod sursa (job #1688290) | Cod sursa (job #2200362) | Cod sursa (job #2549236) | Cod sursa (job #26149)
Cod sursa(job #26149)
#include <cstdio>
#include <stdlib.h>
#define Nmax 100005
struct Trie
{
Trie()
{
fs = fd = NULL;
nod = 0;
}
int nod;
Trie *fs, *fd;
};
const int hmax = 21;
int n, sol = -1, start, stop;
int sir[Nmax], sum[Nmax];
Trie *trie;
void citire()
{
int i;
scanf("%d\n", &n);
for (i = 1; i <= n; ++i)
scanf("%d ", &sir[i]);
}
void baga(int val, int pos)
{
int i;
Trie *cur = trie;
for (i = 20; i >= 0; --i)
{
if ((val >> i) & 1)
{
if (cur -> fd == NULL)
cur -> fd = new(Trie);
cur = cur -> fd;
}
else
{
if (cur -> fs == NULL)
cur -> fs = new(Trie);
cur = cur -> fs;
}
}
cur -> nod = pos;
}
int find(int val, int &pos)
{
int i, ret = 0;
Trie *cur = trie;
for (i = 20; i >= 0; --i)
{
if ((val >> i) & 1)
{
if (cur -> fd != NULL)
{
cur = cur -> fd;
ret += 1 << i;
}
else
cur = cur -> fs;
}
else
{
if (cur -> fs != NULL)
cur = cur -> fs;
else
{
cur = cur -> fd;
ret += 1 << i;
}
}
}
pos = cur -> nod;
return ret;
}
void solve()
{
int i, v, pos;
trie = new(Trie);
baga(0, 0);
for (i = 2; i <= n; ++i)
sir[i] ^= sir[i-1];
for (i = 1; i <= n; ++i)
{
v = ((1 << 21) - 1) ^ sir[i];
v = find(v, pos);
if ((sir[i] ^ v) > sol)
{
sol = v ^ sir[i];
start = pos + 1;
stop = i;
}
baga(sir[i], i);
}
printf("%d %d %d\n", sol, start, stop);
}
int main()
{
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
citire();
solve();
return 0;
}