Pagini recente » Cod sursa (job #1053513) | Cod sursa (job #770555) | Cod sursa (job #2275193) | Cod sursa (job #2101175) | Cod sursa (job #1661436)
#include <fstream>
#include <string.h>
#define nMax 100005
#define BIT 21
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n, val, Max, pozst, pozdr;
int sumxor[nMax];
struct Trie
{
int who;
Trie *fiu[2];
Trie()
{
who=0;
memset(fiu, 0, sizeof(fiu));
}
};
Trie *T=new Trie;
void insert(Trie *node, int bit, int numar, int care)
{
if(bit==-1)
{
node->who=care;
return;
}
bool digit=(1 << bit)&numar;
if(node->fiu[digit]==0)
node->fiu[digit]=new Trie;
insert(node->fiu[digit], bit-1, numar, care);
}
int search(Trie *node, int bit, int numar)
{
if(bit==-1)
return node->who;
bool digit=(1 << bit)&numar;
if(node->fiu[!digit])
return search(node->fiu[!digit], bit-1, numar);
else
return search(node->fiu[digit], bit-1, numar);
}
int main()
{
fin>>n;
insert(T, BIT, 0, 0);
for(int i=1;i<=n;i++)
{
fin>>val;
sumxor[i]=sumxor[i-1]^val;
int poz=search(T, BIT, sumxor[i]);
if(Max<sumxor[i]^sumxor[poz])
{
Max=sumxor[i]^sumxor[poz];
pozst=poz+1;
pozdr=i;
}
insert(T, BIT, sumxor[i], i);
}
fout<<Max<<" "<<pozst<<" "<<pozdr;
return 0;
}