Pagini recente » Cod sursa (job #2416724) | Cod sursa (job #1465178) | Cod sursa (job #328831) | Cod sursa (job #3272024) | Cod sursa (job #1655972)
#include <fstream>
#include <vector>
#include <cmath>
#include <bitset>
using namespace std;
int floorLog2(int x)
{
if (x == 0) return -1;
return (int)floor(log2(x));
}
class TrieNode
{
public:
unsigned int elementCount, nChildren;
int index;
vector<TrieNode*> children;
TrieNode()
{
elementCount = 0;
nChildren = 0;
children.resize(2);
}
};
class Trie
{
public:
TrieNode* root;
int maxDepth;
Trie(int depth)
{
root = new TrieNode;
maxDepth = depth;
}
void Add(int b, int ind)
{
TrieNode *current = root;
for (int i = maxDepth - 1; i >= 0; i--)
{
int idx = (b & (1 << i)) > 0;
if (current->children[idx])
{
current = current->children[idx];
}
else
{
TrieNode* node = new TrieNode;
current->nChildren++;
current->children[idx] = node;
current = node;
}
if (i == 0)
{
current->index = ind;
current->elementCount++;
}
}
}
int findMaxXorIndex(bitset<22> b)
{
TrieNode *current = root;
for (int i = maxDepth - 1; i >= 0; i--)
{
int idx = !b[i];
if (current->children[idx])
{
current = current->children[idx];
}
else if (current->children[!idx])
{
current = current->children[!idx];
}
else return 0;
}
return current->index;
}
};
int getBitsetMinSize(int x)
{
return floorLog2(x) + 1;
}
int main()
{
int n, x, i, maxSize = 0;
vector<int> pXor;
ifstream f("xormax.in");
f >> n;
pXor.resize(n + 1);
pXor[0] = 0;
for (i = 1; i <= n; i++)
{
f >> x;
pXor[i] = pXor[i - 1] ^ x;
int cSize = getBitsetMinSize(pXor[i]);
if (cSize > maxSize)
{
maxSize = cSize;
}
}
int max = pXor[1];
int start, end;
start = end = 1;
Trie t(maxSize);
for (int i = 1; i <= n; i++)
{
t.Add(pXor[i], i);
int maxXorIndex = t.findMaxXorIndex(pXor[i]);
int r = (pXor[i] ^ pXor[maxXorIndex]);
if (r > max)
{
max = r;
start = maxXorIndex + 1;
end = i;
}
}
f.close();
ofstream g("xormax.out");
g << max << " " << start << " " << end;
g.close();
return 0;
}