Pagini recente » Cod sursa (job #1189625) | Cod sursa (job #1780897) | Cod sursa (job #2594472) | Cod sursa (job #116570) | Cod sursa (job #2742514)
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define NMAX 100000
#define INF 2e9
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
int N,x,v[NMAX+5];
struct Trie
{
Trie *fiu[2];
int index;
Trie()
{
index=-1;
fiu[0]=fiu[1]=NULL;
}
};
Trie *T=new Trie;
void ins(Trie *nod,int bit,int index)
{
int bit2=0;
if(bit==-1)
{
nod->index=index;
return;
}
if(((1<<bit)&v[index])!=0)
{
bit2=1;
}
if(nod->fiu[bit2]==NULL)
{
nod->fiu[bit2]=new Trie();
}
ins(nod->fiu[bit2],bit-1,index);
}
int query(Trie *nod,int bit,int index)
{
if(bit==-1)
{
return nod->index;
}
int bit2=0;
if(((1<<bit)&v[index])!=0)
{
bit2=1;
}
if(nod->fiu[1-bit2]!=NULL)
{
return query(nod->fiu[1-bit2],bit-1,index);
}
return query(nod->fiu[bit2],bit-1,index);
}
int main()
{
f>>N;
int vmax=0,start,fin;
ins(T,20,0);
for(int i=1; i<=N; i++)
{
f>>x;
v[i]=v[i-1]^x;
int poz=query(T,20,i);
// if(i==4) cout<<poz<<" ";
if((v[poz]^v[i])>vmax)
{
vmax=v[i]^v[poz];
start=poz+1;
fin=i;
}
ins(T,20,i);
}
g<<vmax<<" "<<start<<" "<<fin;
}