Pagini recente » Cod sursa (job #2842305) | Cod sursa (job #1432290) | Cod sursa (job #33161) | Cod sursa (job #1131568) | Cod sursa (job #2816675)
#include <iostream>
#include <stdio.h>
using namespace std;
const int SIGMA = 2, MAXDEPTH = 21;
struct trie
{
trie *e[SIGMA];
trie()
{
for (int i = 0; i < SIGMA; i++)
e[i] = NULL;
}
};
void getBits(int nr, char bits[]);
void trie_insert(trie *node, char *bit);
int trie_runthrough(trie *node, int depth, char *bit);
int main()
{
char bits[MAXDEPTH + 2];
int nr, maxx, i, n, xorcurr;
trie *root = new trie();
FILE *fin = fopen("xormax.in", "r");
for (i = 0; i <= MAXDEPTH; i++)
bits[i] = 0;
bits[MAXDEPTH + 1] = -1;
trie_insert(root, bits);
fscanf(fin, "%d", &n);
maxx = -1;
xorcurr = 0;
for (i = 0; i < n; i++)
{
fscanf(fin, "%d", &nr);
getBits(nr, bits);
maxx = max(maxx, trie_runthrough(root, 0, bits));
xorcurr ^= nr;
getBits(xorcurr, bits);
trie_insert(root, bits);
}
fclose(fin);
FILE *fout = fopen("xormax.out", "w");
fprintf(fout, "%d", maxx);
fclose(fout);
return 0;
}
void getBits(int nr, char bits[])
{
for (int nrbit = MAXDEPTH; nrbit >= 0; nrbit--)
{
bits[nrbit] = nr & 1;
nr >>= 1;
}
bits[MAXDEPTH + 1] = -1;
}
void trie_insert(trie *node, char *bit)
{
if (*bit == -1)
return;
if (node -> e[*bit] == NULL)
node -> e[*bit] = new trie();
trie_insert(node -> e[*bit], bit + 1);
}
int trie_runthrough(trie *node, int depth, char *bit)
{
if (*bit == -1)
return 0;
if (node -> e[!(*bit)] != NULL)
return (1 << (MAXDEPTH - depth)) + trie_runthrough(node -> e[!(*bit)], depth + 1, bit + 1);
return trie_runthrough(node -> e[*bit], depth + 1, bit + 1);
}