Pagini recente » Cod sursa (job #2440341) | Cod sursa (job #1401583) | Cod sursa (job #2282202) | Cod sursa (job #135268) | Cod sursa (job #1655902)
#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(bitset<22> b, int ind)
{
TrieNode *current = root;
for (int i = maxDepth - 1; i >= 0; i--)
{
int idx = b[i];
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(bitset<22> b)
{
for (int i = b.size() - 1; i >= 0; i--)
{
if (b.test(i))
{
return i + 1;
}
}
return 0;
}
template<std::size_t N>
bool operator<(const std::bitset<N>& x, const std::bitset<N>& y)
{
for (int i = N - 1; i >= 0; i--) {
if (x[i] ^ y[i]) return y[i];
}
return false;
}
template<std::size_t N>
bool operator>(const std::bitset<N>& x, const std::bitset<N>& y)
{
return !(x < y);
}
int main()
{
int n, x, i, maxSize = 0;
vector<bitset<22>> pXor;
ifstream f("xormax.in");
f >> n;
pXor.resize(n + 1);
pXor[0] = bitset<22>(0);
for (i = 1; i <= n; i++)
{
f >> x;
pXor[i] = pXor[i - 1] ^ bitset<22>(x);
int cSize = getBitsetMinSize(pXor[i]);
if (cSize > maxSize)
{
maxSize = cSize;
}
}
int max = pXor[1].to_ulong();
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]).to_ulong();
if (r > max)
{
max = r;
start = maxXorIndex + 1;
end = i;
}
}
f.close();
ofstream g("xormax.out");
g << max << " " << start << " " << end;
g.close();
return 0;
}