Pagini recente » Cod sursa (job #397941) | Cod sursa (job #2802236) | Cod sursa (job #2702614) | Cod sursa (job #995094) | Cod sursa (job #703122)
Cod sursa(job #703122)
#include <cstdio>
#define WIDTH 22
struct trie {
int key;
trie *branch0, *branch1;
trie() {
key = 0;
branch0 = branch1 = 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->branch1)
crtNode->branch1 = new trie;
crtNode = crtNode->branch1;
}
else
{
if (!crtNode->branch0)
crtNode->branch0 = new trie;
crtNode = crtNode->branch0;
}
}
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->branch0)
crtNode = crtNode->branch0;
else if (crtNode->branch1)
{
crtNode = crtNode->branch1;
val |= 1;
}
else
crtNode = crtNode->branch0;
val <<= 1;
}
val >>= 1;
returnValDS = val;
return crtNode->key;
}
int main()
{
int tmp, x, crtXor = 0, bestStart, bestStop, max = 0;
freopen("xormax.in", "r", stdin);
scanf("%d", &n);
insert(0, 0);
for (int i = 1 ; i <= n ; ++i)
{
scanf("%d", &x);
crtXor ^= x;
insert(crtXor, i);
int pos = find(crtXor);
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;
}