Pagini recente » Cod sursa (job #116074) | Cod sursa (job #638636) | Cod sursa (job #2484045) | Borderou de evaluare (job #440441) | Cod sursa (job #1655897)
#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>> v, pXor;
bitset<5> a(5);
bitset<5> b(3);
ifstream f("xormax.in");
f >> n;
v.resize(n + 1);
pXor.resize(n + 1);
pXor[0] = bitset<22>(0);
for (i = 1; i <= n; i++)
{
f >> x;
v[i] = bitset<22>(x);
pXor[i] = pXor[i - 1] ^ v[i];
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;
}