Pagini recente » Cod sursa (job #2764160) | Cod sursa (job #2910165) | Cod sursa (job #1437178) | dm_competition_1 | Cod sursa (job #315870)
Cod sursa(job #315870)
#include <algorithm>
#include <stdio.h>
using namespace std;
class NodTrie
{
public:
int poz, nrFii;
NodTrie *fii[2];
NodTrie()
{
memset(fii, 0, sizeof(fii));
poz = nrFii = 0;
}
};
NodTrie *radTrie = new NodTrie;
int n, sumXor, start = 1, finish = 1, maxGs, locGs;
void addTrie(NodTrie *nod, int level, int key, int place)
{
if (!level)
{
nod->poz = place;
return;
}
level--;
if (!nod->fii[(key & (1 << level)) >> level])
{
nod->nrFii++;
nod->fii[(key & (1 << level)) >> level] = new NodTrie;
}
addTrie(nod->fii[(key & (1 << level)) >> level], level, key, place);
}
int cautaOpus(NodTrie *nod, int level, int key)
{
if (!level)
{
locGs = nod->poz;
return 0;
}
level--;
if (nod->fii[1 ^ ((key & (1 << level)) >> level)])
return ((1 ^ ((key & (1 << level)) >> level)) << level) + cautaOpus(nod->fii[1 ^ ((key & (1 << level)) >> level)], level, key);
else return (key & (1 << level)) + cautaOpus(nod->fii[(key & (1 << level)) >> level], level, key);
}
int main()
{
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
scanf("%d", &n);
addTrie(radTrie, 24, 0, 0);
for (int i = 1; i <= n; i++)
{
int elem;
scanf("%d", &elem);
sumXor ^= elem;
int valMax = cautaOpus(radTrie, 24, sumXor);
if (maxGs < (sumXor ^ valMax))
{
maxGs = (sumXor ^ valMax);
start = locGs + 1;
finish = i;
}
addTrie(radTrie, 24, sumXor, i);
}
printf("%d %d %d\n", maxGs, start, finish);
fclose(stdin);
fclose(stdout);
return 0;
}