Pagini recente » Cod sursa (job #1519146) | Cod sursa (job #1366520) | Cod sursa (job #2022970) | Cod sursa (job #42672) | Cod sursa (job #703514)
Cod sursa(job #703514)
#include <cstdio>
#define WIDTH 30
struct trie {
int key;
trie *b0, *b1;
trie() {
key = 0;
b0 = b1 = 0x0;
};
};
trie *T = new trie;
int n, returnValDS;
void insert(int nr, int pos)
{
trie *crtNode = T;
for (int i = WIDTH - 1; i >= 0 ; --i)
{
if (nr & (1 << i))
{
if (!crtNode->b1)
crtNode->b1 = new trie;
crtNode = crtNode->b1;
}
else
{
if (!crtNode->b0)
crtNode->b0 = new trie;
crtNode = crtNode->b0;
}
}
crtNode->key = pos;
}
int find(int dw)
{
trie *crtNode = T;
int val = 0;
for (int i = WIDTH - 1 ; i >= 0 ; --i)
{
if ((dw & (1 << i)) && crtNode->b0)
crtNode = crtNode->b0;
else if (crtNode->b1)
{
crtNode = crtNode->b1;
val |= 1;
}
else
crtNode = crtNode->b0;
val <<= 1;
}
val >>= 1;
returnValDS = val;
return crtNode->key;
}
int main()
{
int tmp, x, crtXor = 0, bestStart = 1, bestStop = 1, max = -1;
freopen("xormax.in", "r", stdin);
scanf("%d", &n);
insert(0, 0);
for (int i = 1 ; i <= n ; ++i)
{
scanf("%d", &x);
crtXor ^= x;
int pos = find(crtXor);
insert(crtXor, i);
if ((returnValDS ^ crtXor) > max)
{
max = returnValDS ^ crtXor;
bestStart = pos + 1;
bestStop = i;
}
else if ((returnValDS ^ crtXor) == max && (i - pos) < bestStop - bestStart + 1)
{
bestStart = pos + 1;
bestStop = i;
}
}
freopen("xormax.out", "w", stdout);
printf("%d %d %d\n", max, bestStart, bestStop);
return 0;
}