Pagini recente » Cod sursa (job #3185454) | Cod sursa (job #3161771) | Cod sursa (job #3181493) | Cod sursa (job #2892510) | Cod sursa (job #634363)
Cod sursa(job #634363)
#include <fstream>
#include <iostream>
#include <vector>
#include <string.h>
#define MAXN 100001
#define MAX_BITS 21
using namespace std;
typedef unsigned int uint32;
struct TrieData
{
long index;
TrieData *child[2];
};
class CTrie
{
public:
CTrie()
{
memset(Trie.child, 0, 2*sizeof(TrieData*));
}
inline void addElement(const uint32 num, const int index)
{
uint32 i;
int childIndex;
TrieData *ptr = &Trie;
for (i = 1<<MAX_BITS; i; i>>=1)
{
childIndex = !(!(num & i));
if (!ptr->child[childIndex])
{
ptr->child[childIndex] = allocElement();
}
ptr = ptr->child[childIndex];
}
ptr->index = index;
}
long findMaximizingElement(const uint32 num, uint32& val) const
{
uint32 i;
int childIndex;
const TrieData *ptr = &Trie;
val = 0;
for (i = 1<<MAX_BITS; i; i>>=1)
{
childIndex = !(num & i);
if (ptr->child[childIndex])
{
val += i;
ptr = ptr->child[childIndex];
}
else
ptr = ptr->child[!childIndex];
}
return ptr->index;
}
private:
TrieData Trie;
inline TrieData* allocElement() const
{
TrieData *elem = new TrieData;
memset(elem->child, 0, 2*sizeof(TrieData*));
return elem;
}
};
int main()
{
unsigned long x;
uint32 sum = 0;
long maxsum, indMin = 0, indMax=MAXN, N;
fstream fin("xormax.in", fstream::in);
fstream fout("xormax.out", fstream::out);
CTrie Trie;
fin>>N;
fin >> x;
maxsum = x;
indMax = indMin = 0;
Trie.addElement(0, -1);
Trie.addElement(sum, 0);
for (int i=1; i<N; ++i)
{
long index;
uint32 val;
fin >> x;
index = Trie.findMaximizingElement(sum, val);
sum ^= x;
Trie.addElement(sum, i);
if (val > maxsum)
{
maxsum = val;
indMin = index+1;
indMax = i-1;
}
}
fout << maxsum << " " << indMin+1 << " " << indMax+1 << endl;
fin.close();
fout.close();
return 0;
}