Pagini recente » Cod sursa (job #1661559) | Monitorul de evaluare | Istoria paginii utilizator/burcurici | Cod sursa (job #2148640) | Cod sursa (job #2882891)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int nmax=1e5+5;
int n;
int v[nmax];
int maxim,maxput;
int start, ende;
struct Trie
{
int maxpos;
Trie* fii[2];
Trie()
{
maxpos=-1;
fii[0]=NULL;
fii[1]=NULL;
}
} *root;
void add_to_trie(Trie* t, int i, int p)
{
if(p==-1) {
t->maxpos=max(t->maxpos,i);
return;
}
bool pi=( ( (1<<p)&v[i])!=0 );
if(t->fii[pi]==NULL) t->fii[pi]= new Trie;
//t->fii[pi].maxpos=max(t->fii[pi].maxpos, i)
add_to_trie(t->fii[pi], i,p-1);
}
int parcurge_trie(Trie *t, int i, int p)
{
if(p==-1){
return t->maxpos;
}
bool pi=( ( (1<<p)&v[i])==0 );
if(t->fii[pi]==NULL)
{
return parcurge_trie(t->fii[!pi],i,p-1);
}
else return parcurge_trie(t->fii[pi],i,p-1);
}
int main()
{
root = new Trie;
fin>>n;
for(int i=1; i<=n; i++)
{
fin>>v[i];
if(maxim<v[i])
{
maxim=v[i];
start=i;
ende=i;
}
v[i]=(v[i]^v[i-1]);
maxput=max(maxput,(int)log2(v[i]));
}
for(int i=0; i<=n; i++)
{
add_to_trie(root,i,maxput);
int elem=parcurge_trie(root, i,maxput);
if(maxim<(v[elem]^v[i]))
{
maxim=v[elem]^v[i];
start=elem+1;
ende=i;
}
}
fout<<maxim<<" "<<start<<" "<<ende<<" ";
return 0;
}