Pagini recente » Cod sursa (job #473411) | Cod sursa (job #1617264) | Cod sursa (job #1207233) | Cod sursa (job #3180184) | Cod sursa (job #605319)
Cod sursa(job #605319)
#include <fstream>
#include <iostream>
#include <string.h>
#define MAXN 100001
#define MAX_BITS 30
using namespace std;
typedef unsigned int uint32;
uint32 sums[MAXN];
struct TrieData
{
int index;
TrieData *child[2];
};
class CTrie
{
public:
CTrie()
{
Trie.index = -1;
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;
}
inline int findMaximizingElement(const uint32 num) const
{
uint32 i;
int childIndex;
const TrieData *ptr = &Trie;
for (i = 1<<MAX_BITS; i; i>>=1)
{
childIndex = !(num & i);
if (ptr->child[childIndex])
ptr = ptr->child[childIndex];
else
ptr = ptr->child[!childIndex];
}
return ptr->index;
}
private:
TrieData Trie;
inline TrieData* allocElement(const int index = -1) const
{
TrieData *elem = new TrieData;
elem->index = index;
memset(elem->child, 0, 2*sizeof(TrieData*));
return elem;
}
};
int main()
{
unsigned long x, 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;
//cout<<N<<endl;
maxsum=-1;
for (int i=0; i<N; ++i)
{
fin >> x;
sum^=x;
sums[i] = sum;
//cout << sums[i] << " ";
Trie.addElement(sums[i], i);
}
//cout<<endl;
/*for (int i=0; i<N; ++i)
{
for (int j=i+1; j<N; ++j)
{
if ((int)(sums[j]^sums[i]) >= maxsum)
{
maxsum = (sums[j]^sums[i]);
cout << maxsum << " " << i << " " << j << endl;
}
}
}
cout << endl;
cout << "Ref maxsum = " << maxsum << endl;
maxsum = -1;*/
for (int i=0; i<N; ++i)
{
int index = Trie.findMaximizingElement(sums[i]);
int ii = i;
if (index > ii)
{
index ^= ii;
ii ^= index;
index ^= ii;
}
if ((int)(sums[ii]^sums[index]) > maxsum)
{
maxsum = sums[ii]^sums[index];
indMin = index;
indMax = ii;
}
else if ((int)(sums[ii]^sums[index]) == maxsum)
{
long auxMin, auxMax;
//i>index ? (auxMin = index+1, auxMax = i) : (auxMin = i+1, auxMax = index);
auxMin = index;
auxMax = ii;
if (auxMax < indMax)
{
indMin = auxMin;
indMax = auxMax;
}
else if (auxMax == indMax)
{
if ((auxMax - auxMin) < (indMax - indMin))
{
indMin = auxMin;
indMax = auxMax;
}
}
}
}
fout << maxsum << " " << indMin+2 << " " << indMax+1 << endl;
fin.close();
fout.close();
return 0;
}