Pagini recente » Cod sursa (job #92816) | Cod sursa (job #1346241) | Cod sursa (job #2022744) | Cod sursa (job #2938830) | Cod sursa (job #703624)
Cod sursa(job #703624)
#include <cstdio>
#define WIDTH 22
struct trie {
int key;
trie *childs[2];
trie() {
key = 0;
childs[0] = childs[1] = 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)
{
bool branch = nr & (1 << i);
if (!crtNode->childs[branch])
crtNode->childs[branch] = new trie;
crtNode = crtNode->childs[branch];
}
crtNode->key = pos;
}
int find(int dw)
{
trie *crtNode = T;
int val = 0;
for (int i = WIDTH - 1 ; i >= 0 ; --i)
{
bool branch = dw & (1 << i);
if (crtNode->childs[!branch])
{
crtNode = crtNode->childs[!branch];
val |= (!branch);
}
else
{
crtNode = crtNode->childs[branch];
val |= branch;
}
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);
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;
}*/
insert(crtXor, i);
}
freopen("xormax.out", "w", stdout);
printf("%d %d %d\n", max, bestStart, bestStop);
return 0;
}